Submission #530596

#	Time	Username	Problem	Language	Result	Execution time	Memory
530596		perchuts	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	304 KiB

paint

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "paint.h"

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<int>v;
bool solve(string s){
    vector<int>intr,tmp = v;
    // cout<<s<<endl;
    int n = sz(s), where=-1,where2;
    for(int i=0;i<n;++i){
        if(s[i]=='_')continue;
        int p = 0;
        while(i<n&&s[i]!='_'){
            if(s[i]=='X')where = sz(intr),where2=p;
            p++,i++;
        }
        intr.pb(p);
    }   
    if(where==-1){
        reverse(all(tmp));    
        for(int i=0;i<sz(intr);++i){
            int f = 0;
            while(sz(tmp)&&intr[i]>=tmp.back()+f){
                intr[i]-=tmp.back()+f,f=1;tmp.pop_back();
            }
        }
        return sz(tmp)==0;
    }else{
        for(int k=0;k<sz(v);++k){// n^3
            int q = 0, x=where2,exl=0;
            vector<int>intr2 = intr;
            for(int i=0;i<=where;++i){
                int f = 0;exl = f;
                if(q==k)break;
                if(i==where)while(q!=k&&intr2[i]-tmp[q]-f>=tmp[k]&&x-tmp[q]-f>=0)intr2[i]-=tmp[q]+f,x-=tmp[q++]+f,f=1;
                else while(q!=k&&intr2[i]>=tmp[q]+f)intr2[i]-=tmp[q++]+f,f=1;
                exl = f;
            }
            // cout<<k<<" "<<q<<" "<<intr2[where]<<" "<<exl<<endl;
            if(q!=k||max(x+!exl,tmp[k])+exl>intr2[where])continue;
            intr2[where]-=max(x+!exl,tmp[q++])+exl;
            for(int i=where;i<sz(intr2);++i){
                if(q==sz(v))break;
                int f = i==where;
                while(q!=sz(v)&&intr2[i]>=tmp[q]+f)intr2[i]-=tmp[q++]+f,f=1;
            }
            if(q==sz(v))return 1;
        }
        return 0;
    }
    return 0;
}



string solve_puzzle(string s, vector<int> c) {
    string ans;
    v = c;
    for(int i=0;i<sz(s);++i)ans+='0';
    for(int i=0;i<sz(s);++i){
        if(s[i]=='.'){
            bool ok1=0, ok2=0;
            s[i]='X';
            ok1=solve(s);
            // if(ok1)cout<<"Works!\n";
            // else cout<<"No!:(\n";
            s[i]='_';
            ok2=solve(s);
            // if(ok2)cout<<"Works!\n";
            // else cout<<"No!:(\n";
            if(ok1&&ok2)ans[i]='?';
            else if(ok1)ans[i]='X';
            else ans[i]='_';
            s[i]='.';
        }
    }
    for(int i=0;i<sz(s);++i)if(s[i]=='.')s[i]=ans[i];
    return s;
}

// const int S_MAX_LEN = 200 * 1000;
// char buf[S_MAX_LEN + 1];

// int main() {
//     assert(1 == scanf("%s", buf));
//     std::string s = buf;
//     int c_len;
//     assert(1 == scanf("%d", &c_len));
//     std::vector<int> c(c_len);
//     for (int i = 0; i < c_len; i++) {
//         assert(1 == scanf("%d", &c[i]));
//     }
//     std::string ans = solve_puzzle(s, c);


//     cout<<ans.data()<<endl;
//     return 0;
// }

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