Submission #1305294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305294		enzy	Paint By Numbers (IOI16_paint)	C++20	7 / 100	1 ms	348 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){
    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=1;
    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 a=s, 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=1;t<=k;t++){
            vector<int>c1, c2;
            for(int j=1;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<ini;l++) s1.push_back(s[l]);
                for(int l=j+c[t];l<=n;l++) s2.push_back(s[l]);
                if(j+c[t]-1>=i&&j+c[t]-1<=fim){
                    aa|=(get(sz(s1),sz(c1),s1,c1)&&get(sz(s2),sz(c2),s2,c2));
                }
            }
        }
        a[i]='X'; 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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10