Submission #1169131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169131		jbareja	Painting Squares (IOI20_squares)	C++20	45 / 100	30 ms	420 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>

using namespace std;

int k = 62;

vector<int> paint(int n) {
	vector<int> labels(n + 1, 0);
	int i = 0;
	int cnt = 1;
	while (i < n) {
		for (int j=0; j<cnt; j++) {
			int _i = i + j;
			if (_i >= n) break;
			labels[_i] = 0;
		}
		i += cnt;
		if (i >= n) break;
		for (int j=0; j<cnt; j++) {
			int _i = i + j;
			if (_i >= n) break;
			labels[_i] = 1;
		}
		i += cnt;
		cnt++;
	}
	labels[n] = k;

	// for (int i=0; i<n; i++) cout << labels[i]; cout << endl; // <========

	return labels;
}

int find_start_of_segment(int n, int segment_start, int segment_size, int segment_type) {
	int x = 1;
	int i = 0;
	int type = 0;
	while (i < n) {
		// cout << "segment " << type << ", rozmiar " << x << ", poczatek w " << i << endl;
		if (segment_size == x && segment_type == type) return i;
		if (type == 0) {
			i += x;
			type = 1;
		}
		else {
			i += x;
			type = 0;
			x++;
		}
	}
	return -1;
}

int find_location(int n, vector<int> c) {
	int cnt = 0;
	for (int i: c) if (i == -1) cnt++;
	if (cnt > 0) return n + cnt - k;

	// for (int i: c) cout << i; cout << endl; // <==========

	int i = k - 1;
	int cnt_last = 0;
	while (i >= 0 && c[i] == c[k-1]) {
		cnt_last++;
		i--;
	}
	int j = i;
	int cnt_almost_last = 0;
	while (j >= 0 && c[j] == c[i]) {
		cnt_almost_last++;
		j--;
	}

	int segment_size = 0;
	int segment_start = 0;
	int segment_type = 0;
	if (cnt_last > cnt_almost_last) {
		segment_size = cnt_last;
		segment_start = i + 1;
		segment_type = c[segment_start];
	}
	else {
		segment_size = cnt_almost_last;
		segment_start = j + 1;
		segment_type = c[segment_start];
	}

	// cout << cnt_last << " " << cnt_almost_last << endl; // <=========
	// cout << segment_start << " " << segment_size << " " << segment_type << endl; // <========

	int x = find_start_of_segment(n, segment_start, segment_size, segment_type);

	// cout << "x = " << x << endl; // <======

	int res = x - segment_start;

	return res;
}

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