Submission #291681

#	Time	Username	Problem	Language	Result	Execution time	Memory
291681		peti1234	Paint By Numbers (IOI16_paint)	C++17	100 / 100	473 ms	43368 KiB

paint

#include <bits/stdc++.h>

using namespace std;
const int c=200002, p=102;
int n, k, kom[c], dp[c];
string ans;
bool kezd[c][p], veg[c][p], v[c];
string solve_puzzle(string s, vector<int> sz) {
    n=s.size(), k=sz.size();
    s+='.';
    for (int i=0; i<n; i++) kom[i+1]=(s[i]=='_')+kom[i];
    kezd[0][0]=1;
    for (int i=0; i<n; i++) for (int j=0; j<=k; j++) if (kezd[i][j]) {
        //cout << "lehet " << i << " " << j << "\n";
        if (s[i]!='X') kezd[i+1][j]=1;
        if (j<k) {
            int h=sz[j];
            if (i+h<=n && kom[i+h]==kom[i] && s[i+h]!='X') kezd[i+h+1][j+1]=1;
        }
    }
    veg[n][k]=1;
    for (int i=n; i>=1; i--) for (int j=k; j>=0; j--) if (veg[i][j]) {
        //cout << "veg " << i << " " << j << "\n";
        if (s[i-1]!='X') veg[i-1][j]=1;
        if (j) {
            int h=sz[j-1];
            if (i-h-1>=0 && kom[i]==kom[i-h] && s[i-h-1]!='X') veg[i-h-1][j-1]=1;
        }
    }
    for (int i=n; i>=0; i--) for (int j=k; j>=0; j--) if (veg[i][j]) veg[i+1][j]=1;
    /*for (int i=0; i<=n; i++) for (int j=0; j<=k; j++) {
        if (veg[i][j]) cout << "vege " << i << " " << j << "\n";
        if (kezd[i][j]) cout << "kezd " << i << " " << j << "\n";
    }*/
    for (int i=1; i<=n; i++) for (int j=0; j<=k; j++) {
        if (kezd[i][j] && veg[i][j]) v[i]=1;
        //if (i==1 && kezd[i][j] && veg[i][j]) cout << j << "\n";
        if (j<k) {
            int h=sz[j];
            if (i+h<=n+1 && kom[i-1]==kom[i+h-1] && s[i+h-1]!='X' && kezd[i-1][j] && veg[i+h][j+1]) dp[i]++, dp[i+h]--;// cout << "add " << i << " " << i+h << "\n";
            //cout << "valt " << i << " " << i+h << endl;
        }
    }
    for (int i=1; i<=n; i++) {
        dp[i]+=dp[i-1];
        //cout << "vege " << i << " " << dp[i] << " " << v[i] << "\n";
        if (v[i] && dp[i]) ans+='?';
        if (v[i] && !dp[i]) ans+='_';
        if (!v[i] && dp[i]) ans+='X';
    }
    return ans;
}

• 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