Submission #427355

#	Time	Username	Problem	Language	Result	Execution time	Memory
427355		vincentpikachu20	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	300 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> bt;

bool backtrack(string &s, vector<signed> &c, int i, int p){
    int n = s.size(); int k = c.size();
    if(i == k) return true;
    do{
        bool okay = true; int mine = -1;
        for(int j = p; j < p + c[i]; j ++){
            if(s[j] == '_'){ okay = false; mine = j; break; }
        }
        if(okay && (p + c[i] == n || s[p + c[i]] != 'X')){
            bt.push_back(p);
            if(backtrack(s,c,i+1,p + c[i] + 1)) return true;
            bt.pop_back();
        }
        else if(s[p] == 'X') return false;
        else p ++;
    }while(p + c[i] <= n);
    return false;
}

string solve_puzzle(string s, vector<signed> c) {
    int n = s.size(), k = c.size();
    string ans = s;
    //put all to the lefts
    backtrack(s,c,0,0);
    vector<int> l = bt;
    //put all to the rights
    bt.clear();
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    backtrack(s,c,0,0);
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    reverse(bt.begin(), bt.end());
    for(int i = 0; i < k; i ++) bt[i] = n-bt[i]-c[i];
    vector<int> r = bt;
    //apply x's
    for(int i = 0; i < k; i ++){
        for(int j = l[i]; j < r[i] + c[i]; j ++) ans[j] = (ans[j] == '.' ? '?' : ans[j]);
        for(int j = r[i]; j < l[i] + c[i]; j ++) ans[j] = 'X';
    }
    for(char &v : ans) if(v == '.') v = '_';
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool backtrack(std::string&, std::vector<int>&, long long int, long long int)':
paint.cpp:12:31: warning: variable 'mine' set but not used [-Wunused-but-set-variable]
   12 |         bool okay = true; int mine = -1;
      |                               ^~~~

• 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