Submission #615778

#	Time	Username	Problem	Language	Result	Execution time	Memory
615778		IvanJ	커다란 상품 (IOI17_prize)	C++17	Compilation error	0 ms	0 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"

#define pb push_back
#define x first
#define y second

using namespace std;

typedef pair<int, int> ii;

const int maxn = 2e6 + 5;

vector<int> A[maxn];
vector<int> V;
int F = -1;

void check(int x) {
	if(A[x][0] + A[x][1] == 0) F = x;
}

void find(int L, int R) {
	int lo = L, hi = R - 1;
	while(lo <= hi) {
		int mid = (lo + hi) / 2;
		if(A[mid].size() == 0) A[mid] = ask(mid);
		check(mid);
		if(F != -1) return;
		if(A[mid][0] + A[mid][1] < A[hi + 1][0] + A[hi + 1][1]) {V.pb(mid);return;}
		if(A[mid][1] == A[hi][1]) hi = mid - 1;
		else lo = mid + 1;
	}
}

void solve(int lo, int hi, int R) {
	if(lo >= hi) return;
	if(R == 0) return;
	if(R == 1) {find(lo, hi);return;}
	
	int mid = (lo + hi) / 2;
	int mid1 = mid;
	while(1) {
		if(A[mid1].size() == 0) A[mid1] = ask(mid1);
		check(mid);
		if(F != -1) return;
		if(A[mid1][0] + A[mid1][1] < A[hi][0] + A[hi][1]) V.pb(mid1), mid1--;
		else break;
		if(mid1 < lo) break;
	}
	int R1, R2;
	if(mid1 == -1) R2 = R - (mid - mid1);
	else R2 = A[mid1][1] - A[hi][1] - (mid - mid1);
	R1 = R - R2;
	solve(lo, mid1, R1);
	solve(mid + 1, hi, R2);
}

int find_best(int n) {
	if(n <= 5000) {
		for(int i = 0;i < n;i++) {
			A[i] = ask(i);
			if(A[i][0] + A[i][1] == 0) return i;
		}
	}
	int pos = -1;
	int s = 550;
	for(int i = n - 1;i >= n - s;i--) {
		A[i] = ask(i);
		check(i);
		if(F != -1) return F;
		if(pos == -1 || A[i][0] + A[i][1] > A[pos][0] + A[pos][1])
			pos = i;
	}
	
	for(int i = pos + 1;i < n;i++) V.pb(i);
	solve(0, pos, A[pos][0]);
	return F;
}

#include<bits/stdc++.h>
#include "prize.h"

#define pb push_back
#define x first
#define y second

using namespace std;

typedef pair<int, int> ii;

const int maxn = 2e6 + 5;

vector<int> A[maxn];
vector<int> V;
int F = -1;

void check(int x) {
	if(A[x][0] + A[x][1] == 0) F = x;
}

void find(int L, int R) {
	int lo = L, hi = R - 1;
	while(lo <= hi) {
		int mid = (lo + hi) / 2;
		if(A[mid].size() == 0) A[mid] = ask(mid);
		check(mid);
		if(F != -1) return;
		if(A[mid][0] + A[mid][1] < A[hi + 1][0] + A[hi + 1][1]) {V.pb(mid);return;}
		if(A[mid][1] == A[hi][1]) hi = mid - 1;
		else lo = mid + 1;
	}
}

void solve(int lo, int hi, int R) {
	if(lo >= hi) return;
	if(R == 0) return;
	if(R == 1) {find(lo, hi);return;}
	
	int mid = (lo + hi) / 2;
	int mid1 = mid;
	while(1) {
		if(A[mid1].size() == 0) A[mid1] = ask(mid1);
		check(mid);
		if(F != -1) return;
		if(A[mid1][0] + A[mid1][1] < A[hi][0] + A[hi][1]) V.pb(mid1), mid1--;
		else break;
		if(mid1 < lo) break;
	}
	int R1, R2;
	if(mid1 == -1) R2 = R - (mid - mid1);
	else R2 = A[mid1][1] - A[hi][1] - (mid - mid1);
	R1 = R - R2;
	solve(lo, mid1, R1);
	solve(mid + 1, hi, R2);
}

int find_best(int n) {
	if(n <= 5000) {
		for(int i = 0;i < n;i++) {
			A[i] = ask(i);
			if(A[i][0] + A[i][1] == 0) return i;
		}
	}
	int pos = -1;
	int s = 550;
	for(int i = n - 1;i >= n - s;i--) {
		A[i] = ask(i);
		check(i);
		if(F != -1) return F;
		if(pos == -1 || A[i][0] + A[i][1] > A[pos][0] + A[pos][1])
			pos = i;
	}
	
	for(int i = pos + 1;i < n;i++) V.pb(i);
	solve(0, pos, A[pos][0]);
	return F;
}

Compilation message (stderr)

prize.cpp:91:11: error: redefinition of 'const int maxn'
   91 | const int maxn = 2e6 + 5;
      |           ^~~~
prize.cpp:12:11: note: 'const int maxn' previously defined here
   12 | const int maxn = 2e6 + 5;
      |           ^~~~
prize.cpp:93:13: error: redefinition of 'std::vector<int> A [2000005]'
   93 | vector<int> A[maxn];
      |             ^
prize.cpp:14:13: note: 'std::vector<int> A [2000005]' previously declared here
   14 | vector<int> A[maxn];
      |             ^
prize.cpp:94:13: error: redefinition of 'std::vector<int> V'
   94 | vector<int> V;
      |             ^
prize.cpp:15:13: note: 'std::vector<int> V' previously declared here
   15 | vector<int> V;
      |             ^
prize.cpp:95:5: error: redefinition of 'int F'
   95 | int F = -1;
      |     ^
prize.cpp:16:5: note: 'int F' previously defined here
   16 | int F = -1;
      |     ^
prize.cpp:97:6: error: redefinition of 'void check(int)'
   97 | void check(int x) {
      |      ^~~~~
prize.cpp:18:6: note: 'void check(int)' previously defined here
   18 | void check(int x) {
      |      ^~~~~
prize.cpp:101:6: error: redefinition of 'void find(int, int)'
  101 | void find(int L, int R) {
      |      ^~~~
prize.cpp:22:6: note: 'void find(int, int)' previously defined here
   22 | void find(int L, int R) {
      |      ^~~~
prize.cpp:114:6: error: redefinition of 'void solve(int, int, int)'
  114 | void solve(int lo, int hi, int R) {
      |      ^~~~~
prize.cpp:35:6: note: 'void solve(int, int, int)' previously defined here
   35 | void solve(int lo, int hi, int R) {
      |      ^~~~~
prize.cpp:137:5: error: redefinition of 'int find_best(int)'
  137 | int find_best(int n) {
      |     ^~~~~~~~~
prize.cpp:58:5: note: 'int find_best(int)' previously defined here
   58 | int find_best(int n) {
      |     ^~~~~~~~~