Submission #793392

#	Time	Username	Problem	Language	Result	Execution time	Memory
793392		SlavicG	Painting Squares (IOI20_squares)	C++17	0 / 100	87 ms	772 KiB

squares

#include "squares.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1000;
const int K = 10;
int a[N];
map<int, int> mp;
vector<int> generate(int n) {
	mp.clear();
	set<int> nums;
	vector<int> v(n);
	nums.insert((1 << K) - 1);
	for(int i = 0; i < N; ++i) a[i] = 0;
	for(int i = 0; i < K; ++i) a[i] = 1;
	for(int i = 1; i + K - 1 < N; ++i) {
		int number = 0;
		for(int j = 0; j < K; ++j) {
			if(a[i + j]) number += (1 << j);
		}
		if(nums.count(number)) {
			a[i + K - 1] = 1;
		}
		number = 0;
		for(int j = 0; j < K; ++j) {
			if(a[i + j]) number += (1 << j);
		}
		assert(!nums.count(number));
		nums.insert(number);
	}
	for(int i = 0; i < n; ++i) v[i] = a[i];
	for(int i = 0; i + K - 1 < N; ++i) {
		int number = 0;
		for(int j = 0; j < K; ++j) {
			if(a[i + j]) number += (1 << j);
		}
		mp[number] = i;
	}
	return v;
}
std::vector<int> paint(int n) {
	vector<int> labels = generate(n);
	labels.push_back(10);
	return labels;
}
 
int find_location(int n, std::vector<int> c) {
	int number = 0;
	for(int i = 0; i < (int)c.size(); ++i) {
		if(c[i] == -1) {
			return n - i;
		}
		if(c[i] == 1) number += (1 << i);
	}
	return mp[number];
}

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