Submission #1246680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246680		Saul0906	Paint By Numbers (IOI16_paint)	C++20	100 / 100	228 ms	100604 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define fi first
#define se second

using namespace std;

string solve_puzzle(string s, vector<int> c) {
	int n=s.size(), k=c.size(), lst=0;
	int dp[n+1][k+1]{};
	bool vis[n+1][k+1]{};
	dp[0][0]=3;
	rep(i,1,n+1){
		if(s[i-1]=='_') lst=i;
		rep(j,0,k+1){
			if((s[i-1]=='_' || s[i-1]=='.') && dp[i-1][j]) dp[i][j]|=1;
			if(j && i>=c[j-1] && lst<=i-c[j-1]){
				if(i>c[j-1] && dp[i-c[j-1]-1][j-1] && s[i-c[j-1]-1]!='X') dp[i][j]|=2;
				else if(i==c[j-1] && j==1) dp[i][j]|=2;
			}
		}
	}
	int x, y, p[n]{};
	rep(i,0,n) s[i]='X';
	vis[n][k]=true;
	repr(i,n+1,1){
		repr(j,k+1,0){
			if(!vis[i][j]) continue;
			if(dp[i][j]&1) vis[i-1][j]=true, p[i-1]|=1;
			if(dp[i][j]&2){
				p[i-1]|=2;
				if(i>c[j-1]){
					p[i-c[j-1]-1]|=1;
					vis[i-c[j-1]-1][j-1]=true;
				}
				rep(z,i-c[j-1],i) p[z]|=2;
			}
		}
	}
	rep(i,0,n){
		if(p[i]==3) s[i]='?';
		else if(p[i]==0) s[i]='X';
		else if(p[i]==2) s[i]='X';
		else s[i]='_';
	}
	return s;
}

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: 10 / 10
• Subtask 7: 10 / 10