Submission #537784

#	Time	Username	Problem	Language	Result	Execution time	Memory
537784		Cross_Ratio	Paint By Numbers (IOI16_paint)	C++14	59 / 100	14 ms	672 KiB

paint

//#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> DP[105];
int C[105];
bool D[105][105];
int k;
int N;
bool pos(string s) {
    int i, j;
    for(i=0;i<=N;i++) {
        for(j=0;j<=k;j++) D[i][j] = false;
    }
    for(i=0;i<N;i++) {
        for(j=0;j<k;j++) {
            for(int m = 0; m < C[j];m++) DP[i][j][m] = false;
        }
    }
    //cout << s << ' ' << "init\n";
    for(i=0;i<=N;i++) {
        for(j=0;j<k;j++) {
            //cout << i << "th : " << j << '\n';
            if(i!=N) {
                for(int m = 0; m < C[j]; m++) {
                    if(m==0) {
                        if(!j||(i&&D[i-1][j-1])) {
                            if(s[i]!='_') {
                                DP[i][j][m] = true;
                            }
                        }
                    }
                    else {
                        if(i&&DP[i-1][j][m-1]&&(s[i]!='_')) {
                            DP[i][j][m] = true;
                        }
                    }
                    //cout << DP[i][j][m] <<' ';
                }
                //cout << '\n';
            }
            //cout << "init3\n";
            if(i&&(DP[i-1][j][C[j]-1])&&(i==N||s[i]!='X')) {
                //cout << "connected on " << i << ' ' << j << '\n';
                D[i][j] = true;
                //cout << D[i][j] << '\n';
            }
            if(i&&(i==N||s[i]!='X')&&D[i-1][j]) D[i][j] = true;
            //cout << "init4\n";
        }
    }
    /*for(i=0;i<=N;i++) {
        for(j=0;j<k;j++) cout << D[i][j];
        cout << '\n';
    }
    cout << D[N][k-1] << '\n';*/
    return D[N][k-1];
}
string solve_puzzle(string s, vector<int> _C) {
    k = _C.size();
    N = s.length();
    int i, j;
    for(i=0;i<k;i++) C[i] = _C[i];
    N = s.length();
    for(i=0;i<N;i++) {
        DP[i].resize(k);
        for(j=0;j<k;j++) {
            DP[i][j].resize(C[j]);
        }
    }
    string s2;
    s2.resize(N);
    string ans;
    ans.resize(N);
    //.cout << "init\n";
    for(i=0;i<N;i++) {
        if(s[i]!='.') {
            ans[i] = s[i];
            continue;
        }
        for(j=0;j<N;j++) s2[j] = s[j];
        s2[i] = 'X';
        bool p1 = pos(s2);
        s2[i] = '_';
        bool p2 = pos(s2);
        //cout << i << ' ' << p1 << ' ' << p2 << '\n';
        if(p1&&p2) ans[i] = '?';
        else if(p1) ans[i] = 'X';
        else ans[i] = '_';
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10