Submission #1169261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169261		wojtup	Painting Squares (IOI20_squares)	C++20	83.50 / 100	27 ms	416 KiB

squares

#include <bits/stdc++.h>

using namespace std;

vector<int> paint(int n)
{
	vector<int> ret;
	int ile = (n+15)/16;
	for (int i = 0; i < ile; i++) {
		for (int j = 0; j < 7; j++)
			ret.push_back(1);
		ret.push_back(0);
		for (int j = 0; j < 7; j++) {
			bool czyjest = ((i&(1<<j)) != 0);
			ret.push_back(czyjest);
		}
		ret.push_back(0);
	}
	while (ret.size() != n)
		ret.pop_back();
	ret.push_back(16);
	return ret;
}

int find_location(int n, vector<int> c)
{
	int k = c.size();
	if (c.back() == -1) {
		int ile = 0;
		while (c[k-ile-1] == -1)
			ile++;
		return n + ile - k;
	}

	int streak = 0;
	int gdzie = 0;
	for (int i = 0; i < k; i++) {
		if (c[i] == 1)
			streak++;
		if (c[i] == 0)
			streak = 0;
		if (streak == 7) {
			gdzie = i-6;
			break;
		}
	}

	if (streak == 7) {
		bool czysame0suf = true;
		for (int i = k-1; i > gdzie+7; i--)
			if (c[i] != 0) {
				czysame0suf = false;
				break;
			}
		int wyn = 0;
		int wykl = 0;
		for (int i = gdzie+8; i < k; i++) {
			int pot = (1<<wykl);
			wyn += (czysame0suf|c[i]) * pot;
			wykl++;
		}
		for (int i = 0; i < gdzie-1; i++) {
			int pot = (1<<wykl);
			wyn += c[i] * pot;
			wykl++;
		}
		if (czysame0suf)
			wyn++;

		// gowno case 1
		if (gdzie == 0 or gdzie == 1) {
			wyn = 0;
			for (int i = 0; i < 7; i++) {
				int pot = (1<<i);
				wyn += c[i+gdzie+8] * pot;
			}
		}
		// gowno case 2
		if (gdzie == k-7 or gdzie == k-8) {
			wyn = 0;
			for (int i = 0; i < 7; i++) {
				int pot = (1<<i);
				wyn += c[i+gdzie-8] * pot;
			}
			wyn++;
		}

		return 16*wyn - gdzie;
	}

	int idx = 0;
	while (c[idx] == 1)
		idx++;
	idx++;
	int wyn = 0;
	for (int i = 0; i < 7; i++) {
		int pot = (1<<i);
		wyn += c[idx+i] * pot;
	}
	return 16*wyn + 8 - idx;
}

/*mt19937 jd;
int losuj(int a, int b)
{
	return (jd()%(b-a+1)) + a;
}

vector<int> gen(int x, vector<int>& lol)
{
	int k = lol.back();
	vector<int> ret;
	for (int i = x; i < x+k; i++) {
		if (i >= lol.size()-1)
			ret.push_back(-1);
		else
			ret.push_back(lol[i]);
	}
	return ret;
}

int main(void)
{
	int n;
	cin >> n;
	jd.seed(n);
	vector<int> x = paint(n);
	for (int c : x)
		cout << c;
	cout << "\n\n";

	for (int i = 0; i <= 10000; i++) {
		int idx = losuj(0, n-1);
		vector<int> tmp = gen(idx, x);
		int znajdz = find_location(n, tmp);
		if (znajdz == idx)
			cout << "Test #" << i << " ok\r";
		else {
			cout << "Test #" << i << " beka z cb\n";
			cout << "X=" << idx << "  find=" << znajdz << '\n';
			break;
		}
	}

	return 0;
}
*/

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