Submission #309020

#	Time	Username	Problem	Language	Result	Execution time	Memory
309020		georgerapeanu	Painting Squares (IOI20_squares)	C++17	0 / 100	662 ms	748 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);
    
    vector<vector<bool> > viz(1 << 10,vector<bool>(2,false));

    int k = 1;

    while(n - k + 1 > (1 << k)){
        k++;
    }

    int nod = 0;

	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;
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:19:9: warning: unused variable 'nod' [-Wunused-variable]
   19 |     int nod = 0;
      |         ^~~

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