Submission #1043070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043070		thatsgonzalez	Paint By Numbers (IOI16_paint)	C++14	10 / 100	144 ms	596 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;

vector<int> occur1, occur2;
vector<int> arr;
int n;
int k;
int how = 0;

vector<int> p(21);

void calc(int x){
    string res = "";
    for(int i = 0; i<n; i++){
        if(x&p[i]) res+='X';
        else res+='_';
    }

    int cnt = 0;
    int j = 0;
    for(int i = 0; i<n; i++){

        if(res[i] == '_' and cnt){
            if(j==k) return;
            else {
                if(cnt != arr[j]) return;
                else {
                    j++; cnt = 0;
                }
            }
        }
        else if(res[i] == 'X'){
            cnt++;
        }
    }

    if(cnt and j==k) return;
    if(cnt and cnt != arr[j]) return;
    if(cnt and cnt == arr[j] and j+1<k) return;
    if(!cnt and j<k) return;

    how++;

    for(int i = 0; i<n; i++){
        if(res[i] == 'X') occur1[i]++;
        else occur2[i]++;
    }

}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    
    n = s.size();
    k = c.size();

    occur1.assign(n,0);
    occur2.assign(n,0);

    arr = c;

    p[0] = 1;

    for(int i = 1; i<21; i++) p[i]=p[i-1]<<1; 

    for(int i = 0; i<(1<<n); i++){

        calc(i);

    }

    string ans = "";

    for(int i = 0; i<n; i++){
        if(occur1[i] == how) ans+="X";
        else if(occur2[i] == how) ans+="_";
        else ans+="?";
    }

    return ans;


}

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