Submission #999359

#	Time	Username	Problem	Language	Result	Execution time	Memory
999359		ByeWorld	Paint By Numbers (IOI16_paint)	C++14	100 / 100	201 ms	348616 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+10;
const int MAXK = 110;
const int INF = 1e9+10;
typedef pair<int,int> pii;
void chmx(int &a, int b){
	a = max(a, b);
}

int n;
string s, ANS;
int cnt[MAXN];
int dpP[MAXN][MAXK], dpS[MAXN][MAXK], bl[MAXN], wh[MAXN];
int canP[MAXN][MAXK], canS[MAXN][MAXK];
vector <int> c; int k;

string solve_puzzle(string S, vector<int> C) {
	s = '_'+S+'_'; n = s.size()-2;
	for(int i=1; i<=n; i++) cnt[i] = cnt[i-1] + (s[i]=='_');

	c.pb(-1);
	for(auto in : C) c.pb(in);
	k = c.size()-1;

	dpP[0][0] = 1; canP[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){ // a[i] jadi ending dr segment j
			int len = c[j];
			// i-c[j]+1 ... i
			if(i-c[j]+1 <= 0) continue;
			if(cnt[i]-cnt[i-c[j]] != 0) continue;
			if(s[i-c[j]] == 'X') continue; // terakhir jadi X

			if(i-c[j]==0){
				if(canP[i-c[j]][j-1])
					dpP[i][j] = 1;

			} else if(canP[i-c[j]-1][j-1]){
				dpP[i][j] = 1; 
			}
		// cout << i << ' ' << j << ' ' << dpP[i][j] << " dp\n";
		}

		// build canP
		for(int j=0; j<=k; j++){ // a[i] jadi ending dr segment j
			if(s[i] != 'X'){
				canP[i][j] = canP[i-1][j] | dpP[i][j];
			} else { // wajib X
				canP[i][j] = dpP[i][j];
			}
		}
	}
	dpS[n+1][k+1] = 1; canS[n+1][k+1] = 1;
	for(int i=n; i>=1; i--){
		for(int j=k; j>=1; j--){ // a[i] jadi start dr segment j
			int len = c[j];
			// i ... i+c[j]-1
			if(i+c[j]-1 > n) continue;
			if(cnt[i+c[j]-1]-cnt[i-1] != 0) continue;
			if(s[i+c[j]] == 'X') continue; // terakhir jadi X
			
			if(i+c[j]==n+1){
				if(canS[i+c[j]][j+1])
					dpS[i][j] = 1; 

			} else if(canS[i+c[j]+1][j+1]){
				dpS[i][j] = 1; 
			}
			// cout << i << ' ' << j << ' ' << dpS[i][j] << " p\n";
		}

		// build canS
		for(int j=k+1; j>=1; j--){ // a[i] jadi ending dr segment j
			if(s[i] != 'X'){
				canS[i][j] = canS[i+1][j] | dpS[i][j];
			} else { // wajib X
				canS[i][j] = dpS[i][j];
			}
		}
	}

	for(int i=1; i<=n-1; i++){
		for(int j=1; j<=k; j++){
			if(dpP[i][j] && canS[i+2][j+1] && s[i+1] != 'X'){
				bl[i-c[j]+1]++; bl[i+1]--;
			}
		}
	}
	{
		int i=n;
		if(dpP[i][k]){
			bl[i-c[k]+1]++; bl[i+1]--;
		}
	}

	// for(int i=1; i<=3; i++){
	// 	for(int j=0; j<=k+1; j++){
	// 		cout << i << ' ' << j << ' ' << canP[i][j] << " p\n";
	// 	}
	// }
	// for(int i=1; i<=3; i++){
	// 	for(int j=1; j<=k+1; j++){
	// 		cout << i << ' ' << j << ' ' << canS[i][j] << " xx\n";
	// 	}
	// }
	for(int i=1; i<=n; i++){
		for(int j=0; j<=k; j++){
			if(canP[i-1][j] && canS[i+1][j+1]){
				wh[i] = 1;
			}
		}
	}
	
	// for(int i=1; i<=n; i++){
	// 	if(wh[i]) cout << '1';
	// 	else cout << '0';
	// }
	// cout << " pp\n";

	for(int i=1; i<=n; i++) bl[i] += bl[i-1];
	for(int i=1; i<=n; i++){
		if(s[i] != '.'){
			ANS += s[i]; continue;
		}
		if(bl[i] && wh[i]) ANS += '?';
		else if(bl[i]) ANS += 'X';
		else if(wh[i]) ANS += '_';
		else assert(false);
	}
	return ANS;
}

/*
..........
2 3 4

*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:34:8: warning: unused variable 'len' [-Wunused-variable]
   34 |    int len = c[j];
      |        ^~~
paint.cpp:62:8: warning: unused variable 'len' [-Wunused-variable]
   62 |    int len = c[j];
      |        ^~~

• 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