Submission #930151

#	Time	Username	Problem	Language	Result	Execution time	Memory
930151		AlphaMale06	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	604 KiB

paint

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

int black[N], white[N], prb[N], prw[N];

int getwhite(int l, int r){
    return prw[r]-prw[l-1];
}

int getblack(int l, int r){
    return prb[r]-prb[l-1];
}

bool checkvalid(int l, int r){
    if(getwhite(l, r))return 0;
    return 1;
}

void addfakechar(string & s){
    reverse(s.begin(), s.end());
    s+='.';
    reverse(s.begin(), s.end());
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int m = c.size();
    addfakechar(s);
    for(int i=1; i<=n; i++){
        prb[i]=prb[i-1];
        prw[i]=prw[i-1];
        if(s[i]=='_')prw[i]++;
        if(s[i]=='X')prb[i]++;
    }
    int pos[m];
    int p=1;
    int cnt = 0;
    for(int i = 0; i < m; i++){
        while(p<=n){
            if(checkvalid(p, p+c[i]-1)){
                pos[i] = p;
                cnt += getblack(p, p+c[i]-1);
                p += c[i]+1;
                break;
            }
            p++;
        }
    }
    if(cnt==prb[n]){
        white[1]++;
        for(int i=0; i<m; i++){
            black[pos[i]]++;
            black[pos[i]+c[i]]--;
            white[pos[i]]--;
            white[pos[i]+c[i]]++;
        }
    }
    int mv = 0;
    while(true){
        bool changed = 0;
        int nxt;
        if(mv==m-1)nxt=n;
        else nxt=pos[mv+1]-2;
        for(int i = pos[mv]+c[mv]; i<=nxt; i++){
            if(s[i]=='_')continue;
            if(checkvalid(i-c[mv]+1, i)){
                changed = 1;
                cnt-=getblack(pos[mv], pos[mv]+c[mv]-1);
                cnt+=getblack(i-c[mv]+1, i);
                pos[mv]=i-c[mv]+1;
                if(cnt==prb[n]){
                    white[1]++;
                    for(int j=0; j < m; j++){
                        white[pos[j]]--;
                        white[pos[j]+c[j]]++;
                        black[pos[j]]++;
                        black[pos[j]+c[j]]--;
                    }
                }
                break;
            }
        }
        if(changed)mv=max(mv-1, 0);
        else{
            if(mv==m-1)break;
            else mv++;
        }
    }
    for(int i = 2; i <= n; i++){
        white[i]+=white[i-1];
        black[i]+=black[i-1];
    }
    string ret = "";
    for(int i=1; i<=n; i++){
        if(white[i] && black[i])ret+='?';
        else if(white[i])ret+='_';
        else ret+='X';
    }
    return ret;
}

• 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