Submission #367553

#	Time	Username	Problem	Language	Result	Execution time	Memory
367553		BartolM	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1471 ms	186468 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+3;
const int K=104;

int n, k;
vector <int> c;
int dp[N][K][2];
int pref[2][N];
int crn[N], bel[N];
string res;
#define DEBUG 0

int rek(int i, int j, int fl) {
    if (i==n+1) return j==k;

    int &ret=dp[i][j][fl];
    if (ret!=-1) return ret;
    int curr;

    ret=0;
    if (pref[1][i]==pref[1][i-1]) {
        curr=rek(i+1, j, 0);
        if (curr) bel[i]++, ret=1;
    }
    if (!fl && j<k && i+c[j]<=n+1 && pref[0][i+c[j]-1]-pref[0][i-1]==0) {
        curr=rek(i+c[j], j+1, 1);
        if (curr) crn[i]++, crn[i+c[j]]--, ret=1;
    }
    return ret;
}

string solve_puzzle(string s, vector<int> cc) {
    c=cc;
    n=s.size(); k=c.size();
    s=" "+s;
    pref[0][0]=pref[1][0]=0;
    for (int i=1; i<=n; ++i) {
        pref[0][i]=pref[0][i-1]+(s[i]=='_');
        pref[1][i]=pref[1][i-1]+(s[i]=='X');
    }

    memset(dp, -1, sizeof dp);
    memset(crn, 0, sizeof crn);
    memset(bel, 0, sizeof bel);
    assert(rek(1, 0, 0));


    crn[0]=0;
    for (int i=1; i<=n; ++i) crn[i]+=crn[i-1];

    for (int i=1; i<=n; ++i) {
//        if (bel[i] && s[i]=='X') assert(0);
//        if (crn[i] && s[i]=='_') assert(0);

        if (bel[i] && crn[i]) res+='?';
        else if (crn[i]) res+='X';
        else if (bel[i]) res+='_';
        else assert(0);
    }
    return res;
}

• 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