Submission #836324

#	Time	Username	Problem	Language	Result	Execution time	Memory
836324		Victor	Paint By Numbers (IOI16_paint)	C++17	100 / 100	670 ms	180028 KiB

paint

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

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define trav(a,x) for(auto&a:x)

#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

ll n,k;
vll nxt_white,blocks;
string colors;
vll sweep[2];
vector<vll> memo;

ll dp(ll pos,ll block) {
    if(pos==n) {
    //cout<<"pos = "<<pos<<" block = "<<block<<endl;
        return block==k;
    }

    ll&ans=memo[pos][block];
    if(ans!=-1) return ans;

    ans=0;
    if(colors[pos]!='X') { // color white
        ll res=dp(pos+1,block);
        if(res==1) {
            ans=1;
            ++sweep[0][pos];
            --sweep[0][pos+1];
        }
    }

    if(colors[pos]=='X'&&block==k) ans=0;

    if(colors[pos]!='_'&&block<k) {  // color black
        ll npos=pos+blocks[block];
        //if(pos>=4&&block==1) cout<<"bla pos = "<<pos<<" block = "<<block<<endl;
        if(npos<=nxt_white[pos]) {
            if(npos==n||colors[npos]!='X') {
                ll res=dp(min(npos+1,n),block+1);
                if(res) {
                    ans=1;
                    ++sweep[1][pos];
                    --sweep[1][npos];
                    if(npos!=n) {
                        ++sweep[0][npos];
                        --sweep[0][npos+1];
                    }
                }
            }
        }
    }

    return ans;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n=sz(s);
    k=sz(c);
    //cout<<"n = "<<n<<" k = "<<k<<endl;
    rep(i,0,2) sweep[i].assign(n+1,0);
    memo.assign(n,vll(k+1,-1));

    nxt_white.assign(n,0);
    colors=s;
    trav(num,c) blocks.pb(num);

    ll npos=n;
    per(i,0,n) {
        if(colors[i]=='_') npos=i;
        nxt_white[i]=npos;
    }

    assert(dp(0,0));
    string ans="";
    ll white=0,black=0;
    rep(i,0,n) {
        white+=sweep[0][i];
        black+=sweep[1][i];
        if(white&&black) ans+='?';
        else if(white) ans+='_';
        else if(black) ans+='X';
        else assert(0);
    }
    return ans;
}
/*
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>

const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    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