Submission #1245005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245005		santi3223	Paint By Numbers (IOI16_paint)	C++20	7 / 100	1 ms	328 KiB

paint

#include <bits/stdc++.h>
//#include "paint.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

vector<int> c;
vector<pair<bool, bool>> maybe;
//maybe.fi = X, maybe.se = _
ll n, sz;
unordered_set<string> st;
string req;
ll max_emp;

void backt(ll i, ll id_c, string cur){
	ll tamano = st.size();
	st.insert(cur);
	if(tamano == st.size()){
		return;
	}
	if(id_c == c.size() && i <= n+1){
		//cout << "ANS " << cur << "=============================" << ed;
		ff(id, 0, n){
			if(cur[id] == 'X'){
				maybe[id].fi = true;
			}
			else{
				maybe[id].se = true;
			}
		}
		return;
	}
	//cout << i << " " << max_emp << ed;
	if(i >= max_emp){
		/*cout << "TRASH" << cur << ed;
		if(cur == "__XXX_XXXX"){
			cout << id_c << " " << c.size() << " " << i << " " << n << ed;
		}*/
		return;
	}
	string base = cur;
	ll pos = i;
	while(pos < n){
		string str = base;
		ll it = pos;
		while(it-pos < c[id_c]){
			if(it > n){
				return;
			}
			str[it] = 'X';
			it++;
		}
		//cout << "IT " << it << ed;
		if(id_c == c.size()-1){
			//cout << "AFTER " << str << ed;
			backt(it+1, id_c+1, str);
		}
		else{
			if(it > n){
				return;
			}
			str[it] = '_';
			//cout << "AFTER " << str << ed;
			backt(it+1, id_c+1, str);
		}
		
		str = base;
		str[pos] = '_';
		base = str;
		backt(pos+1, id_c, str);
		
		pos++;
	}
	

}

std::string solve_puzzle(std::string s, std::vector<int> C){
	ll taman = 0;
	ff(i, 0, n){
		taman += C[i];
	}
	taman += C.size()-1;
	n = s.size();
	c = C;
	max_emp = n-taman;
	maybe = vector<pair<bool, bool>>(n, {false, false});
	backt(0, 0, s);
	string ans = "";
	ff(i, 0, n){
		bool a = maybe[i].fi, b = maybe[i].se;
		//cout << a << " " << b << ed;
		if(a && b || (!a && !b)){
			ans += '?';
		}
		else if(a && !b){
			ans += 'X';
		}
		else if(!a && b){
			ans += '_';
		}
	}
    return ans;
}
/*
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}
*/

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