Submission #68922

#	Time	Username	Problem	Language	Result	Execution time	Memory
68922		yusufake	Paint By Numbers (IOI16_paint)	C++98	90 / 100	2098 ms	331660 KiB

paint

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

#include "paint.h"

#define ll long long
#define pb push_back
const int N = 2e5 + 0;
//const int S_MAX_LEN = 200 * 1000;
//char buf[S_MAX_LEN + 1];

int M[N][201][2],nex[N],t[N],zer[N],one,n,k;
string s,ans;
vector < int > a;
int f(int i, int j, int h){
    //cout << i << " " << j << " " << h << " aa\n";
    if(i == n) return j==k;
    int &r = M[i][j][h];
    if(r != -1) return r;
    r = 0;
    if(!h && j < k && i+a[j] <= nex[i]) {
        r |= f(i+a[j],j+1,1);
        //cout << i << " " << j << " " << r << "  zz\n";
        if(r){
            t[i]++; t[ i+a[j] ]--; }
    }
    if(s[i] != 'X'){
        int t = f(i+1,j,0);
        r |= t;
        if(t) zer[i]=1;
    }
    return r;
}

string solve_puzzle(string ss, vector <int> aa){
    s = ss;
    a = aa;
    n = s.size();
    k = a.size();
    nex[n] = n;
    int i,j;
    for(i=n-1; i>=0; i--){
        nex[i] = nex[i+1];
        if(s[i] == '_') nex[i] = i;
    }
    memset(M , -1 , sizeof M);
    f(0,0,0);
/*` for(i=0;i<n;i++)
        for(j=0;j<=k;j++)
            if(f(i,j)){
                if(j < k && i+a[j] <= nex[i] && f(i+a[j],j+1)){ 
                    cout << i << " " << j << " ss\n";
                    t[i]++; t[ i+a[i] ]--; }
                if(s[i] != 'X' && f(i+1,j)) zer[i] = 1;
            }
    */
    ll x = 0;
    for(i=0;i<n;i++){
        x += t[i];
        one = x>0;
        if(s[i] != '.'){
            ans.pb(s[i]);
            continue;
        }
        if(zer[i] && one){
            ans.pb('?');
        }
        else if(zer[i]) ans.pb('_');
        else ans.pb('X');
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:41:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^

• 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: 0 / 10