Submission #390226

#	Time	Username	Problem	Language	Result	Execution time	Memory
390226		faresbasbs	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2113 ms	422964 KiB

paint

#include <bits/stdc++.h>
#include "paint.h";
using namespace std;
int n,k,t,lst1,lst2,sum,arr[101],pref[200001],nxt_[200001],nxtX[200001],pre_[200001],preX[200001];
vector<int> segment[102][2];
string s;

int getval(int tag , int tag2 , int a , int b , int curr , int l , int r){
    if(b < l || a > r || b < a){
        return 0;
    }
    if(a <= l && b >= r){
        return segment[tag2][tag][curr];
    }
    int mid = (l+r)/2;
    return max(getval(tag,tag2,a,b,2*curr,l,mid),getval(tag,tag2,a,b,2*curr+1,mid+1,r));
}

void upd(int tag , int tag2 , int pos , int val){
    while(pos){
        segment[tag2][tag][pos] = max(segment[tag2][tag][pos],val);
        pos /= 2;
    }
}

string solve_puzzle(string s , vector<int> c){
    s = "###"+s+"##";
    k = c.size();
    n = s.size()-3;
    t = pow(2,ceil(log2(n+4)));
    for(int i = 0 ; i <= k+1 ; i += 1){
        segment[i][0].resize(2*t,0);
        segment[i][1].resize(2*t,0);
    }
    for(int i = 1 ; i <= n ; i += 1){
        if(s[i] == 'X'){
            break;
        }
        upd(0,0,i+t-1,1);
    }
    for(int i = n+2 ; i >= 1 ; i -= 1){
        if(s[i] == 'X'){
            break;
        }
        upd(1,k+1,i+t-1,1);
    }
    for(int i = 1 ; i <= k ; i += 1){
        arr[i] = c[i-1];
    }
    lst1 = n+2 , lst2 = n+1;
    for(int i = n+2 ; i >= 0 ; i -= 1){
        if(s[i] == 'X'){
            lst1 = i;
        }else if(s[i] == '_'){
            lst2 = i;
        }
        nxt_[i] = lst2 , nxtX[i] = lst1;
    }
    lst1 = 1 , lst2 = 2;
    for(int i = 0 ; i <= n+2 ; i += 1){
        if(s[i] == 'X'){
            lst1 = i;
        }else if(s[i] == '_'){
            lst2 = i;
        }
        pre_[i] = lst2 , preX[i] = lst1;
    }
    for(int i = n ; i >= 3 ; i -= 1){
        for(int j = k ; j >= 1 ; j -= 1){
            if(nxt_[i] < i+arr[j]){
                continue;
            }
            upd(1,j,i+t-1,getval(1,j+1,i+arr[j]+1,nxtX[i+arr[j]],1,1,t));
        }
    }
    for(int i = 3 ; i <= n ; i += 1){
        for(int j = 1 ; j <= k ; j += 1){
            if(pre_[i] > i-arr[j]){
                continue;
            }
            upd(0,j,i+t-1,getval(0,j-1,preX[i-arr[j]],i-arr[j]-1,1,1,t));
        }
    }
    string ans = "";
    for(int i = 3 ; i <= n ; i += 1){
        bool b = 0 , w = 0;
        for(int j = 1 ; j <= k+1 ; j += 1){
            if(s[i] != 'X' && getval(1,j,i+1,nxtX[i],1,1,t) && getval(0,j-1,preX[i],i-1,1,1,t)){
                w = 1;
            }
            if(j <= k && segment[j][1][i+t-1] && getval(0,j-1,preX[i-1],i-2,1,1,t)){
                pref[i] += 1 , pref[i+arr[j]] -= 1;
            }
        }
        sum += pref[i];
        b = (sum > 0 ? 1 : 0);
        if(b && w){
            ans += '?';
        }else if(b){
            ans += 'X';
        }else{
            ans += '_';
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp:2:19: warning: extra tokens at end of #include directive
    2 | #include "paint.h";
      |                   ^

• 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