Submission #1305822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305822		thelegendary08	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2094 ms	1324 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 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; 
int g(int l, int r, vi &ps){
	return ps[r+1] - ps[l];
}
bool check(vi v){
	int n = v.size(), k = c.size(); int cnt = 0; f0r(i,n)if(v[i]==1)cnt++;
	vi ps0(n+1); FOR(i,1,n+1)ps0[i]=ps0[i-1]+(v[i-1]==0);
	vi ps1(n+1); FOR(i,1,n+1)ps1[i]=ps1[i-1]+(v[i-1]==1);
	vector<vector<bool>> dp(n, vector<bool>(k,0)); f0r(i,n){
		if(i+1>=c[0] && g(i-c[0]+1,i,ps0)==0){
			if(ps1[i-c[0]+1]==0){
				dp[i][0]=1; 
			}
		}
		FOR(j,1,k){
			if(i-c[j]+1>=2 && g(i-c[j]+1,i,ps0) == 0){
				if(v[i-c[j]] != 1){
					int ptr = i-c[j]-1; while(ptr >= 0){
						if(v[ptr+1]==1)break;
						if(dp[ptr][j-1]){
							dp[i][j] = 1; break;
						}
						ptr--;
					}
				}
			}
		}
	}
	// if(v[4]==1){
		// // dout(dp[n-1][k-1]);
		// f0r(i,n)cout<<dp[i][0]<<' '; cout<<'\n';
	// }
	if(dp[n-1][k-1])return 1; 
	f0r(i,n-1)if(dp[i][k-1]&&g(i+1,n-1,ps1)==0)return 1; 
	return 0; 
}
std::string solve_puzzle(std::string s, std::vector<signed> C) {
	int n = s.size(); int m = C.size(); for(auto u : C)c.pb(u); string ans = s; vector<vector<bool>>can(n, vector<bool>(2));
	vi v; f0r(i,n)if(s[i]=='X')v.pb(1); else if(s[i] == '_')v.pb(0); else v.pb(-1); 
	f0r(i,n)if(v[i]==-1){
		f0r(j,2){
			vi w = v; w[i] = j; 
			if(check(w))can[i][j]=1;
		}
	} 
	// f0r(i,n){
		// f0r(j,2)cout<<can[i][j]<<' '; cout<<'\n';
	// }
	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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10