oj.uz

Submission #170375

# Submission time Handle Problem Language Result Execution time Memory
170375 2019-12-25T00:55:38 Z workharder Minerals (JOI19_minerals) C++14
40 / 100
 97 ms 6512 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN];
vector<int> mid[MAXN];

int tengah(int x,int y){
	return (3*x+2*y)/5;
}

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]);
				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++){
			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]]);
						}
					}
					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]]);
						}
					}
				}
				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]]);
						}
					}
					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]]);
						}
					}
				}
				if(sudah==N)return;
				prev=nxt;
			}
		}
		prefix=1-prefix;
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 6 ms 2552 KB Output is correct
3 Correct 9 ms 2808 KB Output is correct
4 Correct 16 ms 3192 KB Output is correct
5 Correct 33 ms 3960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2296 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2296 KB Output is correct
4 Correct 3 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 16 ms 3192 KB Output is correct
9 Correct 33 ms 3960 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 22 ms 3448 KB Output is correct
12 Correct 34 ms 4004 KB Output is correct
13 Correct 32 ms 4004 KB Output is correct
14 Correct 36 ms 3960 KB Output is correct
15 Incorrect 97 ms 6512 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -