Submission #761126

#	Time	Username	Problem	Language	Result	Execution time	Memory
761126		raysh07	Paint By Numbers (IOI16_paint)	C++17	Compilation error	0 ms	0 KiB

paint

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

int n, k;
const int N = 2e5 + 69;
const int K = 102;
bool dp1[N][K][2];
bool dp2[N][K][2];
int p[N];
bool b1[N], b2[N];

string solve_puzzle(string s, vector<int> c) {
    n = s.length();
    k = c.size();
    s = "0" + s;
    
    for (int i = 1; i <= n; i++){
        p[i] = p[i - 1];
        if (s[i] == '_') p[i]++;
    }
    
    c.push_back(0);
    for (int i = k; i > 0; i--) c[i] = c[i - 1];
    
    dp1[0][0][0] = true;
    for (int i = 1; i <= n; i++){
        if (s[i] != 'X'){
            for (int j = 0; j <= k; j++){
                dp1[i][j][0] |= dp1[i - 1][j][0] | dp1[i - 1][j][1];
            }
        }
        for (int j = 1; j <= k; j++){
            if (i >= c[j] && p[i] == p[i - c[j]]){
                dp1[i][j][1] |= dp1[i - c[j]][j - 1][0];
            }
        }
        
        // cout << i << "\t";
        // for (int j = 0; j <= k; j++){
        //     cout << dp1[i][j][0] << " " << dp1[i][j][1] << "\t";
        // }
        // cout << "\n";
    }
    
    dp2[n + 1][k + 1][0] = true;
    for (int i = n; i >= 1; i--){
        if (s[i] != 'X'){
            for (int j = 1; j <= k + 1; j++){
                dp2[i][j][0] |= dp2[i + 1][j][0] | dp2[i + 1][j][1];
            }
        }
        for (int j = 1; j <= k; j++){
            if (i + c[j] <= n + 1 && p[i - 1] == p[i + c[j] - 1]){
                dp2[i][j][1] |= dp2[i + c[j]][j + 1][0];
            }
        }
    }
    
    string ans = "";
    
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= k; j++){
            if (dp1[i][j][0] && dp2[i][j + 1][0]){
                b1[i] = true;
            }
        }
        
        for (int j = 1; j <= k; j++){
            for (int finish = i; finish <= min(n, i + c[j] - 1); finish++){
                if (dp1[finish][j][1] && dp2[finish + 1][j + 1][0]) b2[i] = true;
            }
        }
        
        if (b1[i] && b2[i]) ans += '?';
        else if (b1[i]) ans += '_';
        else ans += 'X';
    }
    
    return ans;
}

int main(){
    string s; cin >> s;
    int m; cin >> m;
    vector <int> a(m);
    for (auto &x : a) cin >> x;
    
    cout << solve_puzzle(s, a);
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cctzrM71.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLlc26Z.o:paint.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status