Submission #281596

#	Time	Username	Problem	Language	Result	Execution time	Memory
281596		Mercenary	popa (BOI18_popa)	C++14	100 / 100	144 ms	504 KiB

popa

#ifndef LOCAL
#include "popa.h"
#endif // LOCAL
#include <bits/stdc++.h>
using namespace std;

int solve(int N, int *l, int *r){
    for(int i = 0 ; i < N ; ++i)l[i] = r[i] = -1;
	vector<int> s;
	for(int i = 0 ; i < N ; ++i){
		int son = -1;
		while(s.size() > 0){
			int pos = s.back();
			while(l[pos] != -1)pos = l[pos];
			if(query(pos, i, s.back(), s.back()) == 1){
				break;
			}else{
				son = s.back();
				s.pop_back();
			}
		}
		if(s.size())r[s.back()] = i;
		l[i] = son;
		s.push_back(i);
	}
	return s[0];
}

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