Submission #1305796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305796		thelegendary08	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 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 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; 
bool check(vi v){
	int n = v.size(); int cnt = 0; f0r(i,n)if(v[i]==1)cnt++;
	if(cnt==0){
		vi w; int cur = 0; f0r(i,n){
			if(v[i]==-1)cur++; else{
				if(cur>0)w.pb(cur); cur = 0; 
			}
		}
		if(cur>0)w.pb(cur); cur = 0; 
		int ptr = 0; f0r(i,w.size()){
			int d = w[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
		}
		if(ptr == c.size())return 1; else return 0;
	}
	else{
		vi prev, aft; pii dur = {-1,-1}; int cur = 0, has = 0, pos = 0; f0r(i,n){
			if(v[i]==-1)cur++; 
			else if(v[i]==1){
				pos = cur, cur++, has = 1; 
			}
			else{
				if(has)dur = mp(cur, pos);
				else{
					if(dur.first==-1){
						if(cur>0)prev.pb(cur);
					}
					else{
						if(cur>0)aft.pb(cur);
					}
				}
				has = 0, cur = 0;
			}
		}
		if(has)dur = mp(cur, pos);
		else{
			if(dur.first==-1){
				if(cur>0)prev.pb(cur);
			}
			else{
				if(cur>0)aft.pb(cur);
			}
		}
		
		// vout(v); 
		// vout(prev); 
		// dout2(dur.first,dur.second);
		// vout(aft);
		
		int ptr = 0; f0r(i,prev.size()){
			int d = prev[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
		}
		if(ptr == c.size())ptr--; 
		while(ptr >= 0 && c[ptr] > dur.first)ptr--;
		if(ptr==-1)return 0; 
		vi idk; f0r(i,c[ptr])idk.pb(1); ptr++; while(ptr < c.size()){
			if(idk.size() + c[ptr] + 1 <= dur.first){
				idk.pb(0); f0r(i,c[ptr])idk.pb(1); ptr++;
			}
			else break; 
		}
		if(idk.size()==dur.first && idk[dur.second]==0)ptr--;
		f0r(i,aft.size()){
			int d = aft[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
		}
		if(ptr==c.size())return 1; else 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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10