SRM 495 DIV1 Easy - ColorfulCards

SRM 495 DIV1 Easy - ColorfulCards

10:52

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11302&rd=14424

解き方


すべての状態について、満たすすべての整数を調べていっては
コード量が大変になってしまう。

そこで各状態について、とりうる最小の整数と最大の整数を調べ、
一致していればその整数、一致していない、つまり複数通り存在するならば
−１を返す。

コード


class ColorfulCards {

public: vector<int> theCards(int N, string colors) {
int prime[N+1];
FORE(i,1,N+1)prime[i]=1;
prime[1]=0;
for(int i=2;i<=N;i++)if(prime[i]){
for(int j=i*2;j<=N;j+=i)prime[j]=0;
}

int m=colors.size();
int minx[m],maxx[m];
int at=0;
for(int i=1;i<=N;i++){
if(at>=m)break;
if((colors[at]=='R')==prime[i]){
minx[at++]=i;
}
}
at=m-1;
for(int i=N;i>=1;i--){
if(at<0)break;
if((colors[at]=='R')==prime[i]){
maxx[at--]=i;
}
}

vector<int> ans;
ans.clear();
FORE(i,0,m){
if(minx[i]==maxx[i])ans.push_back(minx[i]);
else ans.push_back(-1);
}

return ans;
}

};

Share this

Google Facebook Twitter More

Related Posts