oj.uz

답안 #170372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170372 2019-12-25T00:37:05 Z workharder Minerals (JOI19_minerals) C++14
40 / 100
 86 ms 7916 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[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;
	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(Query(i)==prev){
			arr[tmpR]=i;
			tmpR++;
		}
		else{
			arr[tmpL]=i;
			tmpL++;
			prev++;
		}
	}
	for(int i=N+1;i<=2*N;i++){
		lo[i]=1;
		hi[i]=N;
		mid[tengah(lo[i],hi[i])].push_back(i);
	}
	int sudah=0,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;
						if(lo[now]<hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else sudah++;
					}
					else{
						lo[now]=i+1;
						if(lo[now]<hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else sudah++;
					}
				}
				else{
					if(nxt==prev){
						lo[now]=i+1;
						if(lo[now]<hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else sudah++;
					}
					else{
						hi[now]=i;
						if(lo[now]<hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else sudah++;
					}
				}
				prev=nxt;
			}
		}
		prefix=1-prefix;
	}
	for(int i=N+1;i<=2*N;i++)Answer(arr[i],arr[lo[i]]);
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 6 ms 2556 KB Output is correct
3 Correct 9 ms 2808 KB Output is correct
4 Correct 15 ms 3448 KB Output is correct
5 Correct 29 ms 4472 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2428 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 3 ms 2424 KB Output is correct
4 Correct 4 ms 2340 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 15 ms 3448 KB Output is correct
9 Correct 29 ms 4472 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 19 ms 3832 KB Output is correct
12 Correct 30 ms 4600 KB Output is correct
13 Correct 29 ms 4728 KB Output is correct
14 Correct 30 ms 4456 KB Output is correct
15 Incorrect 86 ms 7916 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -