oj.uz

Submission #65190

# Submission time Handle Problem Language Result Execution time Memory
65190 2018-08-07T02:12:52 Z spencercompton popa (BOI18_popa) C++14
100 / 100
 129 ms 580 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);
// }
int solve(int n, int* left, int *right){
	for(int i = 0; i<n; i++){
		left[i] = -1;
		right[i] = -1;
	}
	vector<int> tops;
	tops.push_back(0);
	for(int i = 1; i<n; i++){
		vector<int> li;
		while(tops.size()>0){
			if(query(tops.back(),i,i,i)==1){
				li.push_back(tops.back());
				tops.pop_back();
			}
			else{
				break;
			}
		}
		for(int j = 1; j<li.size(); j++){
			right[li[j]] = li[j-1];
		}
		if(li.size()>0){
			left[i] = li.back();
		}
		tops.push_back(i);
	}
	for(int i = 1; i<tops.size(); i++){
		right[tops[i-1]] = tops[i];
	}
	return tops[0];
}
// 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;
// }

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j<li.size(); j++){
                  ~^~~~~~~~~~
popa.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i<tops.size(); i++){
                 ~^~~~~~~~~~~~

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 248 KB Output is correct
2 Correct 15 ms 308 KB Output is correct
3 Correct 10 ms 384 KB Output is correct
4 Correct 13 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 492 KB Output is correct
2 Correct 129 ms 500 KB Output is correct
3 Correct 48 ms 500 KB Output is correct
4 Correct 71 ms 576 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 576 KB Output is correct
2 Correct 94 ms 580 KB Output is correct
3 Correct 100 ms 580 KB Output is correct
4 Correct 101 ms 580 KB Output is correct