oj.uz

Submission #831004

# Submission time Handle Problem Language Result Execution time Memory
831004 2023-08-19T14:53:15 Z Kerim Painting Squares (IOI20_squares) C++17
0 / 100
 3 ms 2584 KB 
#include "squares.h"
#include "bits/stdc++.h"
using namespace std;

const int all = 1023, k = 10;
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 < 10; 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2584 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2512 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2512 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2512 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -