oj.uz

Submission #281596

# Submission time Handle Problem Language Result Execution time Memory
281596 2020-08-23T08:56:32 Z Mercenary popa (BOI18_popa) C++14
100 / 100
 144 ms 504 KB 
#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.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Output is correct
2 Correct 9 ms 256 KB Output is correct
3 Correct 10 ms 256 KB Output is correct
4 Correct 13 ms 256 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 384 KB Output is correct
2 Correct 87 ms 492 KB Output is correct
3 Correct 56 ms 500 KB Output is correct
4 Correct 108 ms 500 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 496 KB Output is correct
2 Correct 106 ms 504 KB Output is correct
3 Correct 96 ms 380 KB Output is correct
4 Correct 144 ms 376 KB Output is correct