Submission #1169106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169106		Roupiq	Painting Squares (IOI20_squares)	C++20	100 / 100	35 ms	748 KiB

squares

#include "squares.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define len(x) (int)(x.size())

template <typename T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
	o << "[";
	for (int i = 0; i < size(v); i++)
	{
		o << (i ? "," : "") << v[i];
	}
	return o << "]";
}

template <typename T1, typename T2>
ostream &operator<<(ostream &o, const map<T1, T2> &v)
{
	o << "{\n";
	for (auto [e, x] : v)
	{
		o << "  " << e << ": " << x << "\n";
	}
	return o << "}";
}
const int maxk = 10;

vector<int> gen(int n = maxk)
{
	vector<string> twoToNth = {""};
	map<string, vector<string>> path;
	for (int i = 0; i < n - 1; i++)
	{
		auto e = move(twoToNth);
		for (auto u : e)
		{
			twoToNth.push_back(u + "1");
			twoToNth.push_back(u + "0");
		}
	}
	for (auto t : twoToNth)
	{
		path[t].push_back((t + "0").substr(1));
		// cout << t << " -> " << path[t].back() << "\n";
		path[t].push_back((t + "1").substr(1));
		// cout << t << " -> " << path[t].back() << "\n";
	}

	// string pos(n - 1, '1');
	string pos(n - 1, '0');
	string res = pos;
	set<string> visited;
	while (true)
	{
		// cout << pos << " -> ";
		char lst = pos[0];
		if (!visited.count(pos + "1"))
			pos = path[pos][1];
		else if (!visited.count(pos + "0"))
			pos = path[pos][0];
		else
			break;
		visited.insert(lst + pos);
		res.push_back(pos.back());
	}

	// cout << twoToNth << "\n";
	// cout << res << "\n";
	vector<int> ress(res.begin(), res.end());
	for (auto &r : ress)
		r -= '0';
	return ress;
}

map<vector<int>, int> prepro(int s)
{
	map<vector<int>, int> res;
	vector<int> p;
	p = gen(s);

	for (int i = 0; i < len(p) - s; i++)
	{
		res[vector<int>(p.begin() + i, p.begin() + i + s)] = i;
	}
	// cout << res << "\n";
	return res;
}

map<vector<int>, int> indexes = prepro(maxk);

std::vector<int> paint(int n)
{
	std::vector<int> labels = gen(maxk);
	labels.resize(n);
	labels.push_back(maxk);
	// cout << labels << "\n";
	return labels;
}

int find_location(int n, std::vector<int> c)
{
	int minuspos = find(c.begin(), c.end(), -1) - c.begin();
	// cout << c << "\n";
	// cout << minuspos << " minuspos\n";
	if(minuspos < len(c))
	{
		return n - minuspos;
	}
	return indexes[c];
}

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