Submission #114793

#	Time	Username	Problem	Language	Result	Execution time	Memory
114793		amiratou	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	2048 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;
int dist_W[200005],close[200005];
bool check_X(string s,vector<int> c,int idx){
	for (int comp = 0; comp < c.size(); ++comp){
		int last=0;
		bool found=1;
		for (int i = 0; i < c.size(); ++i)
		{
			//cout<<last<<"\n";
			if(last>=(s.size())){found=0;break;}
			if(dist_W[last]<(last+c[i])&&dist_W[last]>=last){last=close[dist_W[last]],i--;continue;}
			if(i==comp){
				if(dist_W[last]<idx){last=close[dist_W[last]],i--;continue;}
				if(last>idx){found=0;break;}
				if((idx-last)>=c[i])last=close[idx+2];
				else last=close[c[i]+last+1];
				continue;
			}
			if(last<=idx&&idx<=(last+c[i])){found=0;break;}
			last=close[last+c[i]+1];
		}
		/*cout<<"found:"<<found<<"\n";
		cout<<"idx:"<<idx<<"--------------------\n";*/
		if(found)return 1;
	}
	return 0;
}
bool check_W(string s,vector<int> c,int idx){
	int last=0;
	bool found=1;
	for (int i = 0; i < c.size(); ++i)
	{
		//cout<<last<<"\n";
		if(last>=(s.size())){found=0;break;}
		if(dist_W[last]<(last+c[i])&&dist_W[last]>=last){last=close[dist_W[last]],i--;continue;}
		if(last<=idx){
			if((idx-last)<c[i])last=close[idx+1],i--;
			else last=close[last+c[i]+1];
			continue;
		}
		if((dist_W[last]-last)<c[i])last=close[dist_W[last]],i--;
		else last=close[last+c[i]+1];
	}
	/*cout<<"found:"<<found<<"\n";
	cout<<"idx:"<<idx<<"--------------------\n";*/
	return found;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	for (int i = 0; i < 200005; ++i)
		dist_W[i]=close[i]=s.size();
	int comp=s.size(),comp2=s.size();
	for (int i = s.size()-1; i >=0; --i)
	{
		if(s[i]=='_')comp=i;
		if(s[i]=='.')comp2=i;
		dist_W[i]=comp;
		close[i]=comp2;
	}
	string ph="";
	for (int i = 0; i < s.size(); ++i)
	{
		if(s[i]!='.'){ph+=s[i];continue;}
		bool c1=check_W(s,c,i),c2=check_X(s,c,i);
		if(c1&&c2)ph+="?";
		else if(c1)ph+="_";
		else if(c2)ph+="X";
	}
    return ph;
}

Compilation message (stderr)

paint.cpp: In function 'bool check_X(std::__cxx11::string, std::vector<int>, int)':
paint.cpp:7:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int comp = 0; comp < c.size(); ++comp){
                     ~~~~~^~~~~~~~~~
paint.cpp:10:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < c.size(); ++i)
                   ~~^~~~~~~~~~
paint.cpp:13:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(last>=(s.size())){found=0;break;}
       ~~~~^~~~~~~~~~~~
paint.cpp: In function 'bool check_W(std::__cxx11::string, std::vector<int>, int)':
paint.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < c.size(); ++i)
                  ~~^~~~~~~~~~
paint.cpp:37:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(last>=(s.size())){found=0;break;}
      ~~~~^~~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.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