Submission #1305296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305296		enzy	Paint By Numbers (IOI16_paint)	C++20	59 / 100	76 ms	436 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v.size())
bool get(int n, int k, string s, vector<int> c){
    if(k==0) return true;
    string ret="_";
    // cout << s << " ";
    vector<int>sp(n+1);
    for(int i=1;i<=n;i++){
        sp[i]=sp[i-1];
        if(s[i]=='_') sp[i]++;
    }
    int at=1, i=0;
    while(at<=n){
        if(i<k&&at+c[i]-1<=n&&s[at-1]!='X'&&sp[at+c[i]-1]-sp[at-1]==0&&s[at+c[i]]!='X'){
            for(int j=1;j<=c[i];j++) ret.push_back('X'); // colocando o bloco
            if(at+c[i]<=n) ret.push_back('_'); // dar espaco pro proximo
            at=ret.size();
            i++;
        }else{
            ret.push_back('_');
            at++;
        }
    }
    // cout << ret << " " << at << endl;
    return i==k;
}
string solve_puzzle(string s, vector<int> c){
    int n=s.size(), k=c.size();
    s='_'+s+'_';
    // reverse(c.begin(),c.end()); c.push_back(0); reverse(c.begin(),c.end());
    vector<int>sp(n+1);
    for(int i=1;i<=n;i++){
        sp[i]=sp[i-1];
        if(s[i]=='_') sp[i]++;
    }
    string ret="";
    for(int i=1;i<=n;i++){
        if(s[i]!='.'){
            ret.push_back(s[i]);
            continue;
        }
        string b=s;
        int ini, fim;
        for(int j=i;j>=1;j--){
            if(s[j]=='_') break;
            ini=j;
        }
        for(int j=i;j<=n;j++){
            if(s[j]=='_') break;
            fim=j;
        }
        bool aa=false;
        for(int t=0;t<k;t++){
            vector<int>c1, c2;
            for(int j=0;j<t;j++) c1.push_back(c[j]);
            for(int j=t+1;j<k;j++) c2.push_back(c[j]);
            for(int j=ini;j<=i;j++){
                string s1="", s2="";
                for(int l=1;l<j-1;l++) s1.push_back(s[l]);
                for(int l=j+c[t]+1;l<=n;l++) s2.push_back(s[l]);
                s1='_'+s1+'_'; s2='_'+s2+'_';
                // cout << i << " " << t << ' ' << s1 << " " << s2 << endl;
                // cout << "c1: ";
                // for(int x : c1) cout << x << " ";
                // cout << endl;
                // cout << "c2: ";
                // for(int x : c2) cout << x << " ";
                // cout << endl;
                if(j+c[t]-1>=i&&j+c[t]-1<=fim){
                    aa=(aa||(get(sz(s1)-2,sz(c1),s1,c1)&&get(sz(s2)-2,sz(c2),s2,c2)));
                    // cout << aa << " " << j << " " << get(sz(s1)-2,sz(c1),s1,c1) << " " << get(sz(s2)-2,sz(c2),s2,c2) << endl;
                }
            }
        }
        b[i]='_';
        bool bb=get(n,k,b,c);
        if(aa&&bb) ret.push_back('?');
        else if(aa) ret.push_back('X');
        else if(bb) ret.push_back('_');
        else ret.push_back('A');
    }
    return ret;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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