Submission #482232

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

paint

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

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

ii n, k, a[maxn], b[maxn], dp1[maxn][110][2], dp2[maxn][110][2];
ii ansb[maxn], answ[maxn], ps[maxn], qtdw[maxn];
string ans;
//0->.
//1->_
//2->X

ii sol1(ii i, ii j, ii ant) {
    if(i == 0 && j == 0) return 1;
    if(dp1[i][j][ant] != -1) return dp1[i][j][ant];

    ii ans = 0;

    //if can be white:
    if(i != 0 && a[i] != 2) ans = max(ans, sol1(i-1,j,0));

    //if can be black:
    if(j != 0 && ant == 0 && i-b[j]+1 >= 1 && qtdw[i] - qtdw[i-b[j]] == 0) ans = max(ans, sol1(i-b[j],j-1,1));

    return dp1[i][j][ant] = ans;
}

ii sol2(ii i, ii j, ii ant) {
    if(i == n+1 && j == k+1) return 1;
    if(dp2[i][j][ant] != -1) return dp2[i][j][ant];

    ii ans = 0;

    //if can be white:
    if(i != n+1 && a[i] != 2) ans = max(ans, sol2(i+1,j,0));

    //if can be black:
    if(j != k+1 && ant == 0 && i+b[j]-1 <= n && qtdw[i+b[j]-1] - qtdw[i-1] == 0) ans = max(ans, sol2(i+b[j],j+1,1));

    return dp2[i][j][ant] = ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    string s;
    cin >> s >> k;
    vector<int> c;
    for(ii i = 0; i < k; i++) {
        ii x; cin >> x;
        c.pb(x);
    }

    //begin

    n = s.size();
    k = c.size();
    for(ii i = 1; i <= n; i++) {
        qtdw[i] = qtdw[i-1];
        if(s[i-1] == '.') a[i] = 0;
        else if(s[i-1] == '_') {
            qtdw[i]++;
            a[i] = 1;
        }
        else a[i] = 2;
    }
    for(ii i = 1; i <= k; i++) {
        b[i] = c[i-1];
    }

    for(ii i = 0; i <= n+1; i++) {
        for(ii j = 0; j <= k+1; j++) {
            for(ii ant = 0; ant <= 1; ant++)
                dp1[i][j][ant] = dp2[i][j][ant] = -1;
        }
    }

    for(ii i = 1; i <= n; i++) {
        for(ii j = 1; j <= k+1; j++) {
            //i is white
            if(a[i] != 2) answ[i] = max(answ[i], (sol1(i-1,j-1,0)&sol2(i+1,j,0)) );
        }

        for(ii j = 1; j <= k; j++) {
            //interval (i,i+b[j]-1) black

            if((sol1(i-1,j-1,1)&sol2(i+b[j],j+1,1)) == 1 && qtdw[i+b[j]-1]-qtdw[i-1] == 0) {
                ps[i]++;
                ps[i+b[j]]--;
            }
        }
    }

    for(ii i = 1; i <= n; i++) {
        ps[i]+= ps[i-1];
        if(ps[i] >= 1) ansb[i] = 1;

        if(answ[i] == 1 && ansb[i] == 1)
            ans+= '?';
        else if(answ[i] == 1)
            ans+= '_';
        else if(ansb[i] == 1) 
            ans+= 'X';
        else
            cout << "erro"; 
    }

    cout << ans << endl;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccAdcwkb.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfuf6da.o:paint.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccAdcwkb.o: in function `main':
grader.cpp:(.text.startup+0x20b): undefined reference to `solve_puzzle(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status