Submission #210108

#	Time	Username	Problem	Language	Result	Execution time	Memory
210108		Nucleist	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1024 ms	178756 KiB

paint

#include <bits/stdc++.h> 
#include "paint.h"
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
int n;
vector<int>cal;
string no;
set<int>pos;
int dp[200101][2][101];
int ans1[200101];
pair<int,int>ans2[200101];
int BIT[200101];
int update(int index,int val)
{
	for (index++; index < n+1; index+=(index & (-index)))
	{
		BIT[index]+=val;
	}
}
int query(int index)
{
	int val=0;
	for (index++; index > 0; index-=(index & (-index)))
	{
		val+=BIT[index];
	}
	return val;
}
int update1(int l,int r,int val)
{
	update(l,val);
	update(r+1,-val);
}
int solve(int index,int state,int gr)
{
	if(index==n)
	{
		if(gr==cal.size())return 1;
		else return 0;
	}
	if(dp[index][state][gr]!=-1)return dp[index][state][gr];
	int ans=0;
	if(no[index]=='_' || no[index]=='.')
	{
		ans=max(ans,solve(index+1,0,gr));
	}
	if(ans==1)
	{
		ans1[index]=1;
	}
	int ans3=0;
	if(no[index]=='X' || (no[index]=='.' && state==0))
	{
		auto u=pos.lower_bound(index);
		int next=index+cal[gr]-1;
		if(((*u)>next || u==pos.end()) && no[next+1]!='X' && next+1<=n && gr<=cal.size())
		{
			ans3=max(ans3,solve(next+1,1,gr+1));
		}
	}
	if(ans3==1)
	{
		ans2[index]={1,max(ans2[index].second,index+cal[gr]-1)};
	}
	return dp[index][state][gr]=max(ans,ans3);
}
string solve_puzzle(string s,vector<int>c)
{
	n=s.size();
	cal=c;
	no=s;
	memset(dp,-1,sizeof dp);
	for (int i = 0; i < s.size(); ++i)
	{
		if(s[i]=='_')pos.insert(i);
	}
	solve(0,0,0);
	//debug(1);
	string fin;
	for (int i = 0; i < s.size(); ++i)
	{
		if(ans2[i].first==1)
		{
			update1(i,ans2[i].second,1);
		}
	}
	for (int i = 0; i < s.size(); ++i)
	{
		if(s[i]=='X')fin+='X';
		else if(s[i]=='_')fin+='_';
		else
		{
			int q = query(i);
			if(ans1[i]==1 && q==0)fin+='_';
			else if(ans1[i]==0 && q>=1)fin+='X';
			else fin+='?';
		}
	}
	return fin;
}
//code the AC sol !
// BS/queue/map

Compilation message (stderr)

paint.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
paint.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
paint.cpp: In function 'int update(int, int)':
paint.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
paint.cpp: In function 'int update1(int, int, int)':
paint.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
paint.cpp: In function 'int solve(int, int, int)':
paint.cpp:58:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(gr==cal.size())return 1;
      ~~^~~~~~~~~~~~
paint.cpp:76:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(((*u)>next || u==pos.end()) && no[next+1]!='X' && next+1<=n && gr<=cal.size())
                                                                     ~~^~~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
paint.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
paint.cpp:107: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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10