Submission #501432

#	Time	Username	Problem	Language	Result	Execution time	Memory
501432		PoPularPlusPlus	Paint By Numbers (IOI16_paint)	C++17	100 / 100	771 ms	489356 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

string solve_puzzle(string s , vector<int> c){
    int n = s.size(); 
    int k = c.size();
    int pre[n];
    if(s[0] == '_')pre[0] = 1;
    else pre[0] = 0;
    for(int i = 1; i < n; i++){
        pre[i] = pre[i-1] + (s[i] == '_');
    }
    bool zero[n][k + 1] , one[n][k+1];;
    memset(zero , 0 , sizeof zero);
    memset(one,0,sizeof one);
    if(s[0] != 'X')zero[0][0] = 1;
    if(c[0] == 1){
        if(s[0] != '_')one[0][1] = 1;
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= k; j++){
            if(s[i] == '_'){
                zero[i][j] = max(zero[i-1][j] , one[i-1][j]);
            }
            else {
                if(s[i] == 'X'){
                    if(j == 0){
                        continue;
                    }
                    if(c[j-1] <= i + 1){
                        if(c[j-1] == i + 1){
                            if(pre[i] == 0 && j == 1)one[i][j] = 1;
                            else one[i][j] = 0;
                        }
                        else {
                            int sum = pre[i] - pre[i - c[j-1]];
                            if(sum == 0)one[i][j] = zero[i - c[j-1]][j - 1];
                        }
                    }
                    else one[i][j] = 0;
                }
                else {
                    zero[i][j] = max(zero[i-1][j] , one[i-1][j]);
                    if(j != 0){
                        if(c[j-1] <= i + 1){
							if(c[j-1] == i + 1){
								if(pre[i] == 0 && j == 1){
									one[i][j] = 1;
								}
							}
							else {
								int sum = pre[i] - pre[i - c[j-1]];
								if(sum == 0){
									one[i][j] = zero[i-c[j-1]][j-1];
								}
							}
						}
					}
				}
			}
		}
	}
    string ans = "";
    int cur = n - 1;
    vector<pair<int,int>> v[n];
    v[n-1].pb(mp(k,0));
    v[n-1].pb(mp(k,1));
    int last = n;
    bool there[n][k + 1][2];
    memset(there , 0 , sizeof there);
    while(cur >= 0){
		bool zero1 = 0 , one1 = 0;
		for(auto i : v[cur]){
			//if(cur == 2 && i.vs == 1)cout << i.vf << '\n';
			if(i.vs == 0){
				zero1 = max(zero1 , zero[cur][i.vf]);
				if(cur - 1 >= 0 && zero[cur][i.vf] == 1){
					if(there[cur-1][i.vf][1] == 0){
						v[cur-1].pb(mp(i.vf , 1));
						there[cur-1][i.vf][1] = 1;
					}
					if(there[cur-1][i.vf][0] == 0){
						v[cur-1].pb(mp(i.vf , 0));
						there[cur - 1][i.vf][0] = 1;
					}
				}
				continue;
			}
			one1 = max(one1 , one[cur][i.vf]);
			if(one[cur][i.vf] == 1  && i.vf - 1 >= 0 && cur - c[i.vf-1] >= -1){
				if(cur - c[i.vf-1] >= 0 && there[cur - c[i.vf-1]][i.vf-1][0] == 0){
					v[cur - c[i.vf-1]].pb(mp(i.vf - 1 , 0));
					there[cur - c[i.vf-1]][i.vf-1][0] = 1;
				}
				last = min(last , (cur - c[i.vf-1]) + 1);
			}
		}
		if(last <= cur)one1 = 1;
		if(one1 && zero1)ans += '?';
		else if(one1)ans += 'X';
		else ans += '_';
		cur--;
	}
	reverse(all(ans));
	return ans;
}
/*
void solve(){
	string s;
	cin >> s;
	int k;
	cin >> k;
	vector<int> v(k);
	for(int i = 0; i < k; i++)cin >> v[i];
	cout << solve_puzzle(s , v) << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("dec.in", "r", stdin);
//freopen("dec.out", "w", stdout);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}
*/

• 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