Submission #319087

#	Time	Username	Problem	Language	Result	Execution time	Memory
319087		CaroLinda	Painting Squares (IOI20_squares)	C++14	100 / 100	212 ms	852 KiB

squares

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

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )

const int MAX = 10 ;

using namespace std ;

vector<int> eulerCycle , seq ;
set< pair<int,int> > usedEdges ;

void findLabels()
{
	eulerCycle.clear() ;
	usedEdges.clear() ;

	stack<int> st ;
	st.push(0) ;

	while(!st.empty() )
	{
		int x = st.top() ;

		int neigh1 = x>>1 ;

		if( usedEdges.find(make_pair(x, neigh1) ) == usedEdges.end() )
		{	
			st.push(neigh1) ;
			usedEdges.insert(make_pair(x,neigh1) ) ;
			continue ;
		}

		int neigh2 = neigh1 | (1<<(MAX-2) ) ;

		if(usedEdges.find(make_pair(x,neigh2) ) == usedEdges.end() )
		{
			st.push(neigh2) ;
			usedEdges.insert(make_pair(x,neigh2) ) ; 
			continue ;
		}

		eulerCycle.push_back(x) ;
		st.pop() ;

	}



	reverse(all(eulerCycle) ) ;

	for(int i = 0 ; i < MAX-1 ; i++ ) seq.push_back(0) ;

	for(int i = 0 ; i < sz(eulerCycle)-1 ; i++ )
	{
		int x = eulerCycle[i] ;
		int y = eulerCycle[i+1] ;

		if( y == (x>>1) ) seq.push_back(0) ;
		else seq.push_back(1) ;

	}

	for(int i = 0 ; i< 10 ; i++ ) seq.push_back(-1) ;

}

vector<int> paint(int n) 
{

	//you must return a vector<labels> of size n+1
	//the last is k

	findLabels() ;

	vector<int> labels(n+1) ;

	for(int i = 0 ; i < n ; i++ ) labels[i] = seq[i] ;
	labels[n] = MAX ;

	return labels ;

}

bool achei = false ;

int find_location(int n, std::vector<int> c) {

	if(!achei)
	{
		achei = true ;
		findLabels() ;
	}
		
	int cnt = 0 ;

	for(int i = 0 ; i < sz(c) ; i++ ) 
		if(c[i] == -1 ) cnt++ ;

  	if(cnt != 0 )
		return n - (sz(c)-cnt) ;

	for(int i = 0 ; i+sz(c)-1 < sz(seq) ; i++ )
	{
		bool ok = true ;
		for(int j = i , jj = 0 ; jj < sz(c) ; jj++ , j++ )
			if(seq[j] != c[jj] ) ok = false ;

		if(ok )return i ;

	}



}

Compilation message (stderr)

squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

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