Submission #165828

#	Time	Username	Problem	Language	Result	Execution time	Memory
165828		Segtree	Paint By Numbers (IOI16_paint)	C++14	59 / 100	9 ms	396 KiB

paint

#include"paint.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
string solve_puzzle(string s,vector<int> c){
    int n=s.size();
    vector<int> t;
    ll sum=0;
    for(int i=0;i<c.size();i++){
	if(i){
	    t.push_back(1);
	    sum+=1;
	}
	t.push_back(c[i]);
	sum+=c[i];
    }
    
    ll sl[210],sr[210];
    ll bef=0;
    sl[0]=0;
    for(int i=0;i<t.size();i++){
	while(1){
	    if(i%2==0){
		ll nxt=1e17;
		for(int j=bef;j<n;j++){
		    if(s[j]=='_'){
			nxt=j+1;
			break;
		    }
		}
		if(bef+t[i]<nxt)break;
		else bef=nxt;
	    }
	    if(i%2==1){
		ll nxt=1e17;
		for(int j=bef;j<n;j++){
		    if(s[j]=='X'){
			nxt=j+1;
			break;
		    }
		}
		if(bef+t[i]<nxt)break;
		else bef=nxt;
	    }
	}
	bef+=t[i];
	sl[i+1]=bef;
    }
    
    bef=n-1;
    sr[t.size()]=n-1;
    for(int i=t.size()-1;i>=0;i--){
	while(1){
	    if(i%2==0){
		ll nxt=-1e17;
		for(int j=bef;j>=0;j--){
		    if(s[j]=='_'){
			nxt=j-1;
			break;
		    }
		}
		if(bef-t[i]>nxt)break;
		else bef=nxt;
	    }
	    if(i%2==1){
		ll nxt=-1e17;
		for(int j=bef;j>=0;j--){
		    if(s[j]=='X'){
			nxt=j-1;
			break;
		    }
		}
		if(bef-t[i]>nxt)break;
		else bef=nxt;
	    }
	}
	bef-=t[i];
	sr[i]=bef;
    }//cout<<"$"<<n<<" "<<t.size()<<endl;
    
    bool b[110],w[110];
    for(int i=0;i<n;i++)b[i]=w[i]=0;
    
    for(int i=0;i<n;i++){
	for(int j=-1;j<=(int)t.size();j++){
	    ll l=0,r=n-1;
	    if(j>-1)l=sl[j];
	    if(j<(int)t.size())r=sr[j+1];
	    //if(i==0)cout<<j<<":"<<l<<" "<<r<<endl;
	    if(not(r-l+1>=t[j]&&l<=i&&i<=r))continue;
	    
	    if(0<=j&&j<(int)t.size()){
		bool th=0;
		for(int k=l;k<=r-t[j]+1;k++){
		    if(not(k<=i&&i<k+t[j]))continue;
		    bool ok=1;
		    for(int p=0;p<t[j];p++){
			if(j%2==0&&s[k+p]=='_')ok=0;
			if(j%2!=0&&s[k+p]=='X')ok=0;
		    }
		    
		    //if(i==4&&ok==1)cout<<"%%%"<<k<<endl;
		    if(ok)th=1;
		}
		if(th==0)continue;
	    }
	    
	    if(j%2==0)b[i]=1;
	    else w[i]=1;
	}
    }
    
    string ans;
    for(int i=0;i<n;i++){
	//if(b[i]==0&&w[i]==0)cout<<1/0<<endl;
	if(b[i]==0&&w[i]==1)ans+="_";
	if(b[i]==1&&w[i]==0)ans+="X";
	if(b[i]==1&&w[i]==1)ans+="?";
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:10:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<c.size();i++){
                 ~^~~~~~~~~
paint.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<t.size();i++){
                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10