Submission #1307851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307851		thelegendary08	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2 ms	352 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
vi c; vvi ps; 
int g(int l, int r, int d){
	return ps[d][r+1] - ps[d][l];
}
std::string solve_puzzle(std::string s, std::vector<signed> C) {
	int n = s.size(); int k = C.size(); for(auto u : C)c.pb(u); string ans = s; vector<vector<int>>can(n, vector<int>(2));
	vi v; f0r(i,n)if(s[i]=='X')v.pb(1); else if(s[i] == '_')v.pb(0); else v.pb(-1); 
	ps.resize(2); f0r(i,2)ps[i].resize(n+1); FOR(i,1,n+1)f0r(j,2)ps[j][i] = ps[j][i-1] + (v[i-1] == j);
	vector<vector<int>> dp(n+1, vector<int>(k+1)), rdp(n+1, vector<int>(k+1)); 
	int has = 0; dp[0][0] = 1; FOR(i,1,n+1){if(v[i-1]==1)has=1; if(!has)dp[i][0]=1;}
	FOR(i,1,n+1)FOR(j,1,k+1){
		if(v[i-1]==0||v[i-1]==-1)dp[i][j] |= dp[i-1][j];
		if(v[i-1]==1||v[i-1]==-1)dp[i][j] |= (i-c[j-1] >= 0 && g(i-c[j-1],i-1,0)==0 && (i-c[j-1]==0||v[i-c[j-1]-1]!=1) && 
		((i-c[j-1]-1>=0 && dp[i-c[j-1]-1][j-1]) || (j==1 && i-c[j-1] == 0)));
	}
	reverse(v.begin(),v.end()); reverse(c.begin(),c.end());
	has = 0; rdp[0][0] = 1; FOR(i,1,n+1){if(v[i-1]==1)has=1; if(!has)rdp[i][0]=1;}
	FOR(i,1,n+1)FOR(j,1,k+1){
		if(v[i-1]==0||v[i-1]==-1)rdp[i][j] |= rdp[i-1][j];
		if(v[i-1]==1||v[i-1]==-1)rdp[i][j] |= (i-c[j-1] >= 0 && g(i-c[j-1],i-1,0)==0 && (i-c[j-1]==0||v[i-c[j-1]-1]!=1) && 
		((i-c[j-1]-1>=0 && rdp[i-c[j-1]-1][j-1]) || (j==1 && i-c[j-1] == 0)));
	}
	reverse(v.begin(),v.end()); reverse(c.begin(),c.end());
	f0r(i,n)if(v[i]==-1){
		f0r(j,k+1)can[i][0] |= (dp[i][j] && rdp[n-i-1][k-j]);
	} 
	f0r(i,k){
		vector<bool> cn(n); 
		for(int j = 0; j + c[i] - 1 < n; j++){
			cn[j] = (g(j,j+c[i]-1,0)==0 && (j==0||v[j-1]!=1) && (j+c[i]==n||v[j+c[i]]!=1) &&
			((j>0 && dp[j-1][i]) || (j==0&&i==0)) && 
			((n-j-c[i]-1>=0&&rdp[n-j-c[i]-1][k-i-1]) || (n-j-c[i]-1==-1 && i==k-1)));
		}
		// vout(cn);
		vi cf(n+1); f0r(j,n)if(cn[j])cf[j]++,cf[j+c[i]]--;
		int cur = 0; f0r(j,n){
			cur += cf[j]; if(cur > 0)can[j][1]=1;
		}
	}
	f0r(i,n)if(v[i]==-1){
		if(can[i][0]&&can[i][1])ans[i]='?'; else if(can[i][0])ans[i]='_'; else ans[i]='X';
	}
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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