oj.uz

Submission #65180

# Submission time Handle Problem Language Result Execution time Memory
65180 2018-08-07T00:26:21 Z spencercompton popa (BOI18_popa) C++14
61 / 100
 148 ms 628 KB 
#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
// int gc(int a, int b){
// 	if(a==0 || b==0){
// 		return a+b;
// 	}
// 	return gc(b%a,a);
// }
// vector<int> inp;
// int query(int a, int b, int c, int d){
// 	int x = inp[a];
// 	int y = inp[c];
// 	for(int i = a; i<=b; i++){
// 		x = gc(x,inp[i]);
// 	}
// 	for(int i = c; i<=d; i++){
// 		y = gc(y,inp[i]);
// 	}
// 	return (x==y?1:0);
// }
vector<int> le;
vector<int> ri;
int f(int l, int r){
	if(l>r){
		return -1;
	}
	if(l==r){
		le[l] = -1;
		ri[r] = -1;
		return l;
	}
	int p1 = l;
	int p2 = r;
	bool fi = true;
	while(p1<=p2){
		fi = !fi;
		int i = p1;
		if(fi){
			i = p2;
		}
		if(query(l,r,i,i)==1){
			le[i] = f(l,i-1);
			ri[i] = f(i+1,r);
			return i;
		}
		if(fi){
			p2--;
		}
		else{
			p1++;
		}
	}
	assert(false);
	return -69;
}

int solve(int n, int* left, int *right){
	le.resize(n);
	ri.resize(n);
	int ret = f(0,n-1);
	for(int i = 0; i<n; i++){
		left[i] = le[i];
		right[i] = ri[i];
	}
	return ret;
}
// int main(){
// 	inp.push_back(12);
// 	inp.push_back(4);
// 	inp.push_back(16);
// 	inp.push_back(2);
// 	inp.push_back(2);
// 	inp.push_back(20);
// 	int a[6];
// 	int b[6];
// 	cout << solve(6,a,b) << endl;
// 	for(int i = 0; i<6; i++){
// 		cout << a[i] << " ";
// 	}
// 	cout << endl;
// 	for(int i = 0; i<6; i++){
// 		cout << b[i] << " ";
// 	}
// 	cout << endl;
// }

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 248 KB Output is correct
2 Correct 7 ms 476 KB Output is correct
3 Correct 23 ms 476 KB Output is correct
4 Correct 16 ms 476 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 520 KB Output is correct
2 Correct 114 ms 628 KB Output is correct
3 Correct 133 ms 628 KB Output is correct
4 Correct 148 ms 628 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 628 KB too many queries
2 Halted 0 ms 0 KB -