Submission #434212

#	Time	Username	Problem	Language	Result	Execution time	Memory
434212		TLP39	Painting Squares (IOI20_squares)	C++14	100 / 100	434 ms	66524 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[512];

void init_adj()
{
	for(int i=0;i<512;i++)
	{
	adj[i].clear();	
		adj[i].push_back((i<<1)%512);
		adj[i].push_back(((i<<1)%512)+1);
}
}

vector<int> cyc;
stack<int> path;
int appear[1024];
vector<int> labels;
void get_cycle()
{
	cyc.clear();
	path.push(0);
	int temp;
	while(!path.empty())
	{
		if(adj[path.top()].size())
		{
			temp=adj[path.top()][adj[path.top()].size()-1];
			adj[path.top()].pop_back();
			path.push(temp);
		}
		else
		{
			cyc.push_back(path.top());
			path.pop();
		}
	}
	for(int i=0;i<9;i++) labels.push_back(0);
	for(int i=0;i<1024;i++)
	{
		appear[(cyc[cyc.size()-1]<<1)+(cyc[cyc.size()-2]&1)]=i;
		cyc.pop_back();
		labels.push_back(cyc[cyc.size()-1]&1);
}
}

vector<int> paint(int n) {
	labels.clear();
	init_adj();
get_cycle();
while(labels.size()>n) labels.pop_back();
labels.push_back(min(n,10));
	return labels;
}

int find_location(int n, std::vector<int> c) {
	init_adj();
	get_cycle();
	if(c[min(n,10)-1]==-1)
	{
		for(int i=0;i<=9;i++) if(c[i]==-1) return n-i;
		return -1;
	}
	if(n<10) return 0;
	int code=0;
	for(int i=0;i<=9;i++)
	{
		code+=c[i]<<(9-i);
	}
	return appear[code];
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:53:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 | while(labels.size()>n) labels.pop_back();
      |       ~~~~~~~~~~~~~^~

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