제출 #380857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380857		VodkaInTheJar	popa (BOI18_popa)	C++14	100 / 100	110 ms	608 KiB

popa

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

using namespace std;


int solve(int n, int *left, int *right)
{
	int last = 0; 
	left[last] = right[last] = -1;
	
	vector <int> par(n);
	par[last] = -1; 
	
	for (int i = 1; i < n; i++)
	{
		int prv = last;
		while (last != -1 && !query(last, i, last, last))
		{
			prv = last;
			last = par[last];
		}
		
		if (last == -1)
		{
			par[i] = -1; 
			par[prv] = i;
			left[i] = prv;
			right[i] = -1; 
		}
		
		else 
		{
			if (right[last] == -1)
			{
				right[last] = i;
				left[i] = -1; 
				right[i] = -1; 
			    par[i] = last; 
			}
			
			else 
			{
				left[i] = right[last];
				par[left[i]] = i;
				right[i] = -1; 
				right[last] = i; 
				par[i] = last; 
			}
		}
		
		last = i;
	}
	
	while (par[last] != -1)
	last = par[last];
	
	return last; 
}

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39