Submission #309019

#	Time	Username	Problem	Language	Result	Execution time	Memory
309019		georgerapeanu	Painting Squares (IOI20_squares)	C++17	0 / 100	130 ms	548 KiB

squares

#include "squares.h"
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

vector<int> paint(int n) {
	vector<int> labels(n + 1, 1);
	return labels;
}

int find_location(int n, vector<int> c) {
    if(c.back() == -1){
        for(int i = 0;i < (int)c.size();i++){
            if(c[i] == -1){
                return n - ((int)c.size() - i) - 1;
            }
        }
    }
    
    vector<int> labels = paint(n);

    int k = labels.back();

    int curr = 0,target = 0;

    for(auto it:c){
        target = target * 2 + it;
    }

    for(int i = 0;i < k;i++){
        curr = curr * 2 + labels[i];
    }

    for (int i = 0;i < n - k + 1;i++){
        if(curr == target){
            return i;
        }
        curr = (curr * 2 + labels[i + k]) - (labels[i] << (k + 1));
    }

	return 0;
}

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