oj.uz

답안 #170368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170368 2019-12-24T23:52:03 Z workharder Minerals (JOI19_minerals) C++14
40 / 100
 61 ms 7924 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 (x+y)/2;
}

void Solve(int N) {
	int prev=0,tmpL=1,tmpR=N+1,nxt;
	for(int i=1;i<=2*N;i++){
		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 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 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 8 ms 2808 KB Output is correct
4 Correct 13 ms 3240 KB Output is correct
5 Correct 23 ms 4216 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 4 ms 2296 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2556 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 13 ms 3240 KB Output is correct
9 Correct 23 ms 4216 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 18 ms 3836 KB Output is correct
12 Correct 24 ms 4260 KB Output is correct
13 Correct 17 ms 4216 KB Output is correct
14 Correct 18 ms 4092 KB Output is correct
15 Incorrect 61 ms 7924 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -