Submission #836362

#	Time	Username	Problem	Language	Result	Execution time	Memory
836362		TB_	Paint By Numbers (IOI16_paint)	C++17	100 / 100	701 ms	109616 KiB

paint

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

#define ll long long
#define deb(x) cout << #x << " = " << x << endl
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

ll n, k;
vl prefPos = {0}, prefNeg = {0}, gc;
vvi memo;
vpl ans; // pos, neg


bool dp(int pos, int a){
    if(pos >= n) return k == a;
    int &res = memo[pos][a];
    if(res != -1) return res;
    res = 0;
    if(!(prefPos[pos+1]-prefPos[pos]) && dp(pos+1, a)){
        res = 1;
        ans[pos].F = 1;
    }
    if(a == k) return res;
    if(pos+gc[a]<=n && !(prefNeg[pos+gc[a]]-prefNeg[pos]) && !(prefPos[pos+gc[a]+1]-prefPos[pos+gc[a]]) && dp(pos+gc[a]+1, a+1)){
        res = 1;
        ans[pos].S++;
        ans[pos+gc[a]].S--;
        ans[pos+gc[a]].F = 1;
    }

    return res;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n = s.length(); k = c.size();
    s.pb('.');
    fo(i, n+1){
        prefPos.pb((s[i] == 'X'?1:0));
        prefNeg.pb((s[i] == '_'?1:0));
        prefPos[i+1] += prefPos[i];
        prefNeg[i+1] += prefNeg[i];
    }
    fo(i, k) gc.pb(c[i]);
    memo.assign(n+1, vi(k+1, -1));
    ans.assign(n+5, pl{0, 0});
    dp(0, 0);
    string sendString = "";
    pl current;
    fo(i, n){
        current.F = ans[i].F;
        current.S += ans[i].S;
        // deb2(current.F, current.S);
        // deb2(ans[i].F, ans[i].S);
        if(current.F&&!current.S) sendString.pb('_');
        else if(!current.F&&current.S) sendString.pb('X');
        else sendString.pb('?');
    }

    return sendString;
}


// 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