Submission #1305289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305289		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;
string get(int n, int k, string s, vector<int> c, vector<int> sp){
    string ret="_";
    int at=1, i=1;
    while(at<=n){
        if(i<=k&&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
            ret.push_back('_'); // dar espaco pro proximo
            at=ret.size();
            i++;
        }else{
            ret.push_back('_');
            at++;
        }
    }
    return ret;
}
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]++;
    }
    vector<vector<int>>pd(k+1);
    for(int i=1;i<=k;i++){
        for(int j=1;j+c[i]-1<=n;j++){
            // checar se o comeco pode ser em j
            // condicoes: s[j-1]!='X', [j,j+c[i]-1] n tem '_', s[j+c[i]], s[j+c[i]]!='X'
            if(s[j-1]!='X'&&sp[j+c[i]-1]-sp[j-1]==0&&s[j+c[i]]!='X') pd[i].push_back(j); 
        }
    }
    // cout << "yay" << endl;
    vector<int>white(n+1,0), black(n+1,0), first(k+1), last(k+2);
    first[1]=pd[1][0]; last[k]=pd[k].back();
    for(int i=2;i<=k;i++){
        for(int j : pd[i]){
            if(first[i-1]+c[i-1]+1<=j){ // da pra coloca-lo e sobra um branco entre eles
                first[i]=j;
                break;
            }
        }
    }
    for(int i=k-1;i>=1;i--){
        for(int j : pd[i]) if(j+c[i]+1<=last[i+1]) last[i]=j; // da pra me colocar e ainda sobra
    }
    for(int i=1;i<=k;i++){
        for(int x : pd[i]){
            // cout << first[i] << " " << x << " " << last[i] << endl;
            if(first[i]<=x&&x<=last[i]){
                // cout << x << " " << x+c[i] << endl;
                black[x]++, black[x+c[i]]--;
            }
        }
    }
    // for(int i=1;i<=n;i++) cout << black[i] << " ";
    // cout << endl;
    // cout << "yey" << endl;
    string ex=get(n,k,s,c,sp), ret="";
    // cout << "yiy" << endl;
    white[1]++; white[max(last[1],1)]--;
    // for(int i=1;i<=k;i++) cout << first[i] << " " << last[i] << endl; 
    for(int i=1;i<k;i++){
        white[first[i]+c[i]]++;
        white[last[i+1]]--;
    }
    if(first[k]+c[k]!=n) white[first[k]+c[k]]++;
    // for(int i=1;i<=n;i++) cout << white[i] << " ";
    // cout << endl;
    int sum_w=0, sum_b=0;
    for(int i=1;i<=n;i++){
        sum_w+=white[i]; sum_b+=black[i];
        if(sum_w&&sum_b) ret.push_back('?');
        else if(sum_w) ret.push_back('_');
        else if(sum_b) ret.push_back('X');
        else ret.push_back('A');
    }
    return ret;
}
// passa pro vazio?

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