oj.uz

답안 #319087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319087 2020-11-03T22:54:59 Z CaroLinda Painting Squares (IOI20_squares) C++14
100 / 100
 212 ms 852 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 852 KB Output is correct
2 Correct 212 ms 684 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 784 KB Output is correct
2 Correct 189 ms 788 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 808 KB Output is correct
2 Correct 201 ms 832 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 816 KB Output is correct
2 Correct 204 ms 852 KB Output is correct