Submission #1169212

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

squares

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
#define all(a) a.begin(), a.end()
#define print(a) for (auto elem:a) cout<<elem<<' '; cout<<'\n'
#define segprep(b) resize(1<<((int)ceil(log2(b.size()))+1))
#define FOR(a) for (int _ = 0; _ < a; _++)

const int k = 69, sect_size = 27;

vi paint(int n) {
	vi labels(n+1, 0);
	labels.back() = k;
    int sect_cnt = n/sect_size;
    for (int section = 0; section < sect_cnt; section++){
        int sect_start = 27*section;
        for (int i = sect_start+6; i < sect_start+6+7; i++){
            labels.at(i) = 1;
        }
        // 7 bitow bialych
        for (int i = sect_start+6+7+7; i < sect_start+6+7+7+7; i++){
            labels.at(i) = 1;
        }
        for (int i = 0; i < 6; i++){
            labels.at(sect_start+i) = (bool)(section&(1<<i));
        }
    }
    fill(labels.begin()+sect_size*sect_cnt, labels.end()-1, 1);

    return labels;
}

int find_location(int n, vi c) {
    // assert((int)c.size() == k); //////////////////////
	if (find(all(c), -1) != c.end()){
		return n-(find(all(c), -1)-c.begin());
	}

    int seven_zeros_start;
    bool found;
	for (int i = 0; i < k-7; i++){
        found = true;
        for (int j = i; j < i+7; j++){
            if (c.at(j) != 0){
                found = false;
                break;
            }
        }
        if (found){
            seven_zeros_start = i;
            break;
        }
    }
    int ind_num_start = seven_zeros_start+14;
    int section = 0;
    for (int i = 0; i < 6; i++){
        if (c.at(i+ind_num_start)){
            section += 1<<i;
        }
    }
    int real_num_start = section*27;
    return real_num_start-ind_num_start;
}

/*
static int max_k = 0;
static int r, n, k_, q, x;
static std::vector<int> labels, c, answers;

int main() {
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++) {
		assert(scanf("%d%d", &n, &q) == 2);
		labels = paint(n);
		if ((int)labels.size() != n + 1) {
			printf("Number of labels not equal to %d\n", n + 1);
			exit(0);
		}
		for (int i = 0; i < n; i++) {
			if (labels[i] != 0 && labels[i] != 1) {
				printf("Label not 0 or 1\n");
				exit(0);
			}
		}
		k_ = labels[n];
		if (k_ < 0 || k_ > 1000) {
			printf("Label not in range 0 to 1000\n");
			exit(0);
		}
		if (k > max_k) {
			max_k = k_;
		}
		for (int i = 0; i < q; i++) {
			assert(scanf("%d", &x) == 1);
			c.clear();
			
			for (int j = x; j < x + k_; j++) {
				if (j >= n) {
					c.push_back(-1);
				} else {
					c.push_back(labels[j]);
				}
			}
			answers.push_back(find_location(n, c));
		}
	}
	printf("%d\n", max_k);
	for (int ans : answers) {
		printf("%d\n", ans);
	}
	exit(0);
}
*/

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