Submission #226487

#	Time	Username	Problem	Language	Result	Execution time	Memory
226487		infinite_iq	Paint By Numbers (IOI16_paint)	C++14	100 / 100	749 ms	105080 KiB

paint

    #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    #include <bits/stdc++.h>
    using namespace std;
    #define sqr 200
    #define mid (l+r)/2
    #define pb push_back
    #define ppb pop_back
    #define fi first
    #define se second
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define era erase
    #define C continue
    #define mem(dp,i) memset(dp,i,sizeof(dp))
    #define mset multiset
    typedef long long ll;
    typedef short int si;
    typedef long double ld;
    typedef pair<int,int> pi;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pi> vpi;
    typedef vector<pll> vpll;
    const ll mod=1e9+7;
    const ll inf= 4e18;
    const ld pai=acos(-1);
    #include "paint.h"
    #include <cstdlib>
    int n ,k ;
    string s;
    int a[200009];
    int bs[200009];
    int yes[200009][2];
    int dp[200009][109];
    void upd(int l,int r,int t){
            yes[l][t]++;
            yes[r+1][t]--;
    }
    int sum(int l,int r){
            if ( l>r || r>=n )return -1;
            int x=bs[r];
            if(l)x-=bs[l-1];
            return x;
    }
    int bt(int id,int crnt){
            if(id==n)return (crnt==k);
            int &ret=dp[id][crnt];
            if(ret!=-1) return ret;
            ret=0;
            if(s[id]=='_'){
                    ret=bt(id+1,crnt);
            }
            if(s[id]=='.'){
                    ret=bt(id+1,crnt);
                    if(ret>0)upd(id,id,0);
                    int z=1;
                    if(crnt<k){
                            int l=id,r=id+a[crnt]-1;
                            int Sum=sum(l,r);
                            if(Sum!=a[crnt]) z=0;
                            if(r+1<n && s[r+1]=='X') z=0;
                            if(z){
                                    z=bt(min(r+2,n),crnt+1);
                                    if(z){
                                            upd(l,r,1);
                                            upd(r+1,r+1,0);
                                    }
                            }
                            ret=max(ret,z);
                    }
            }
            if(s[id]=='X' && crnt<k){
                    int l=id,r=id+a[crnt]-1;
                    int Sum=sum(l,r);
                    if(Sum!=a[crnt])return ret=0;
                    if(r+1<n && s[r+1]=='X') return ret=0;
                    ret=bt( min(r+2,n) ,crnt+1);
                    if(ret){
                            upd(l,r,1);
                            upd(r+1,r+1,0);
                    }
            }
            else if(s[id]=='X')return ret=0;
            return ret;
    }
    string solve_puzzle(string S , vector<int> c) {
            mem(dp,-1);
            s=S;
            n=S.size();
            k=c.size();
            for(int i=0;i<n;i++){
                    bs[i]=(s[i]!='_');
                    if(i)bs[i]+=bs[i-1];
            }
            for(int i=0;i<k;i++)a[i]=c[i];
            bt(0,0);
            for(int i=1;i<n;i++){
                    for(int j=0;j<2;j++){
                            yes[i][j]+=yes[i-1][j];
                    }
            }
            string ans="";
            for(int i=0;i<n;i++){
                    if(s[i]!='.'){
                            ans+=s[i];
                            C;
                    }
                    if(yes[i][0] && yes[i][1])ans+='?';
                    else if(yes[i][0])ans+='_';
                    else 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