oj.uz

Submission #170377

# Submission time Handle Problem Language Result Execution time Memory
170377 2019-12-25T01:02:06 Z workharder Minerals (JOI19_minerals) C++14
0 / 100
 38 ms 2424 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const double RAT=1.618;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN];
vector<int> mid[MAXN];

int tengah(int x,int y){
	double hai=(RAT*x+1.0*y)/(RAT+1.0);
	return (int)hai;
}

void Solve(int N) {
	int prev=0,tmpL=1,tmpR=N+1,nxt,sudah=0,C=0;
	vector<int> v;
	for(int i=1;i<=2*N;i++)v.push_back(i);
	random_shuffle(v.begin(),v.end());
	for(auto i : v){
		if(tmpL==N+1 || Query(i)==prev){
			arr[tmpR]=i;
			lo[tmpR]=C+1;
			hi[tmpR]=tmpL-1;
			if(lo[tmpR]<hi[tmpR])mid[tengah(lo[tmpR],hi[tmpR])].push_back(tmpR);
			else{
				Answer(i,arr[tmpL-1]);
				arr[tmpL-1]=0;
				sudah++;
			}
			tmpR++;
			if(tmpL==tmpR-N)C=tmpL-1;
		}
		else{
			arr[tmpL]=i;
			tmpL++;
			prev++;
		}
	}
	if(sudah==N)return;
	int prefix=0;
	while(sudah<N){
		for(int i=1;i<=N;i++){
			if(arr[i])prev=Query(arr[i]);
			while(!mid[i].empty()){
				int now=mid[i].back();
				mid[i].pop_back();
				nxt=Query(arr[now]);
				if(prefix){
					if(nxt==prev){   //sudah ada
						hi[now]=i-1;
						res[now]=i;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
							arr[now]=0;arr[res[now]]=0;
						}
					}
					else{
						lo[now]=i+1;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
							arr[now]=0;arr[res[now]]=0;
						}
					}
				}
				else{
					if(nxt==prev){
						lo[now]=i+1;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
							arr[now]=0;arr[res[now]]=0;
						}
					}
					else{
						hi[now]=i-1;
						res[now]=i;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
							arr[now]=0;arr[res[now]]=0;
						}
					}
				}
				if(sudah==N)return;
				prev=nxt;
			}
		}
		prefix=1-prefix;
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 2424 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2296 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -