oj.uz

Submission #380857

# Submission time Handle Problem Language Result Execution time Memory
380857 2021-03-23T10:18:03 Z VodkaInTheJar popa (BOI18_popa) C++14
100 / 100
 110 ms 608 KB 
#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.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 12 ms 364 KB Output is correct
3 Correct 12 ms 384 KB Output is correct
4 Correct 9 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 492 KB Output is correct
2 Correct 79 ms 480 KB Output is correct
3 Correct 60 ms 364 KB Output is correct
4 Correct 91 ms 364 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 364 KB Output is correct
2 Correct 92 ms 364 KB Output is correct
3 Correct 80 ms 608 KB Output is correct
4 Correct 110 ms 492 KB Output is correct