Submission #319086

#	Time	Username	Problem	Language	Result	Execution time	Memory
319086		CaroLinda	Painting Squares (IOI20_squares)	C++14	0 / 100	3101 ms	33708 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 ;

}

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

	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:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^

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