Submission #831029

#	Time	Username	Problem	Language	Result	Execution time	Memory
831029		Kerim	Painting Squares (IOI20_squares)	C++17	0 / 100	3 ms	2768 KiB

squares

#include "squares.h"
#include "bits/stdc++.h"
using namespace std;
 
const int k = 15;
const int all = (1<<k) - 1;
string S;
unordered_set<int> visited;
void rec(int pos, int mask, string s){
    if (pos == 0){
        S = s;
        return;
    }
    for (int i = 0; i < 3; i++){
        int coin = rand()%2;
        if (coin == 0){
            int new_mask = ((mask*2)&all);
            if ((int)s.size() >= k-1){
                if (!visited.count(new_mask)){
                    visited.insert(new_mask);
                    s += '0';
                    rec(pos-1, new_mask, s);
                    visited.erase(new_mask);
                    break;
                }
            }
            else{
                s += '0';
                rec(pos-1, new_mask, s);
                break;
            }
        }
        else{
            int new_mask = ((mask*2+1)&all);
            if ((int)s.size() >= k-1){
                if (!visited.count(new_mask)){
                    visited.insert(new_mask);
                    s += '1';
                    rec(pos-1, new_mask, s);
                    visited.erase(new_mask);
                    break;
                }
            }
            else{
                s += '1';
                rec(pos-1, new_mask, s);
                break;
            }
        }
    }
    s.pop_back();
}
 
void build(int n, int seed = 55){
	S.clear();
    srand(seed);
    rec(n, 0, "");;
	assert(!S.empty());
}
 
vector<int> paint(int n) {
	vector<int> labels(n + 1, 1);
	build(n);
	for (int i = 0; i < n; i++)
		labels[i] = S[i] - '0';
	labels[n] = k;
	return labels;
}
 
int find_location(int n, vector<int> c) {
	int r = c.size();
	if (c[r-1] == -1){
		int answer = n;
		for (int i = 0; i < r; i++)
			if (c[i] >= 0)
				answer -= 1;
		return answer;
	}
	build(n);
	string t;
	for (auto x: c)
		t += x + '0';
	for (int i = 0; i <= n-r; i++)
		if (S.substr(i, r) == t)
			return i;
	return -1;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55