読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

SRM 704 Div1

DIV1は座ってるだけになるのでアレ

【Easy TreeDistanceConstruction】

既出だったのにバグらせた。
m-iをm-1にしていて終了(サンプルが弱すぎる。
C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder

class TreeDistanceConstruction {
public:

  vector <int> construct(vector <int> d) {
    vector<int> res;
    int n=d.size();
    int m=0;
    int t[111]={};
    queue<int> q[111];
    for(int i=0;i<n;i++){
      t[d[i]]++;
      q[d[i]].push(i);
      m=max(m,d[i]);
    }
    bool f=1;
    for(int i=0;i<(m+1)/2;i++) f&=t[m-i]>=2;
    if(m%2) f&=t[m/2+1]==2;
    else f&=t[m/2]==1;
    for(int i=0;i<n;i++){
      if(m%2) f&=d[i]>=m/2+1;
      else f&=d[i]>=m/2;
    }
    if(!f) return res;
    
    bool used[111]={};

    int b[111][2]={};

    if(m%2){
      for(int i=0;i<=m/2;i++){
	b[m-i][0]=q[m-i].front();q[m-i].pop();
	b[m-i][1]=q[m-i].front();q[m-i].pop();
	used[b[m-i][0]]=1;
	used[b[m-i][1]]=1;
	if(i){
	  res.push_back(b[m-i+1][0]);
	  res.push_back(b[m-i][0]);
	  res.push_back(b[m-i+1][1]);
	  res.push_back(b[m-i][1]);
	}
	if(i==m/2){
	  res.push_back(b[m-i][0]);
	  res.push_back(b[m-i][1]);
	}
      }
      for(int i=0;i<n;i++){
	if(used[i]) continue;
	res.push_back(i);
	res.push_back(b[d[i]-1][0]);
      }
    }else{
      for(int i=0;i<m/2;i++){
	b[m-i][0]=q[m-i].front();q[m-i].pop();
	b[m-i][1]=q[m-i].front();q[m-i].pop();
	used[b[m-i][0]]=1;
	used[b[m-i][1]]=1;
	if(i){
	  res.push_back(b[m-i+1][0]);
	  res.push_back(b[m-i][0]);
	  res.push_back(b[m-i+1][1]);
	  res.push_back(b[m-i][1]);
	}
      }
      b[m/2][0]=q[m/2].front();q[m/2].pop();
      used[b[m/2][0]]=1;
      res.push_back(b[m/2+1][0]);
      res.push_back(b[m/2][0]);
      res.push_back(b[m/2+1][1]);
      res.push_back(b[m/2][0]);
      
      for(int i=0;i<n;i++){
	if(used[i]) continue;
	res.push_back(i);
	res.push_back(b[d[i]-1][0]);
      }
    }

    return res;
  }
}
【全体】

1258 -> 1332 (+74)
1258 -> 1227 (-31)
システムテストが落ちてる人も通っている換算になっていたらしくてつらい。
コンテスト中にEasy解けるようになりたいなあ