Submission #240353

#	Time	Username	Problem	Language	Result	Execution time	Memory
240353		lyc	Paint By Numbers (IOI16_paint)	C++14	100 / 100	390 ms	332664 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 2e5+5;
const int mxK = 105;

int N, K, C[mxK];
string S;
int pw[mxN];
int l[2][mxN][mxK], r[2][mxN][mxK], w[mxN], b[mxN];

string solve_puzzle(string s, vector<int> c) {
    N = SZ(s), S = '^' + s, K = SZ(c);
    FOR(i,1,K){ C[i] = c[i-1]; }
    pw[0] = 0;
    FOR(i,1,N) pw[i] = pw[i-1] + (S[i] == '_');
    C[0] = N+10; // make sure C[0] cannot be used
    FOR(f,0,1) { l[f][0][0] = 1; FOR(j,1,K) l[f][0][j] = 0; }
    FOR(i,1,N){
        FOR(j,0,K){
            l[1][i][j] = (S[i] != 'X' && (l[1][i-1][j] || l[0][i-1][j]));
            l[0][i][j] = (i-C[j]+1 >= 1 && pw[i]-pw[i-C[j]] == 0 && l[1][i-C[j]][j-1]);
        }
    }
    C[K+1] = N+10; // make sure C[K+1] cannot be used
    FOR(f,0,1) { r[f][N+1][K+1] = 1; FOR(j,1,K) r[f][N+1][j] = 0; }
    RFOR(i,N,1){
        FOR(j,1,K+1){
            r[1][i][j] = (S[i] != 'X' && (r[1][i+1][j] || r[0][i+1][j]));
            r[0][i][j] = (i+C[j]-1 <= N && pw[i+C[j]-1]-pw[i-1] == 0 && r[1][i+C[j]][j+1]);
        }
    }
    FOR(i,1,N){
        FOR(j,0,K){
            if (l[1][i][j] && r[1][i][j+1]) w[i] = 1;
            if (l[0][i][j] && r[1][i+1][j+1]) ++b[i-C[j]+1], --b[i+1];
        }
    }
    string ans(N,'?');
    FOR(i,1,N){
        b[i] += b[i-1];
        ans[i-1] = (w[i] == 0 ? 'X' : (b[i] == 0 ? '_' : '?'));
    }
    return ans;
}

• 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