oj.uz

답안 #128919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128919 2019-07-11T10:55:39 Z roseanne_pcy Minerals (JOI19_minerals) C++14
80 / 100
 54 ms 2804 KB 
#include "minerals.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int last = 0;

int ask(int x)
{
	return Query(x);
}

int n;
vector<int> Left, Right;

int match[maxn];

void solve(int L, int M, int R, vector<int> vec)
{
	// printf("solving [%d %d]\n", L, R);
	// for(int i = 1; i< (int) vec.size(); i++) printf("%d ", vec[i]); printf("\n");
	if(L == R)
	{
		// last = ask(Right[L]);
		match[vec[1]] = Right[L];
		return;
	}
	vector<int> v1, v2;
	v1.pb(0); v2.pb(0);
	// printf("last = %d\n", last);
	for(int x : vec)
	{
		if(!x) continue;
		int y = ask(x);
		if(y == last) v1.pb(x);
		else v2.pb(x);
		last = y;
	}
	int M1 = (L+M)/2, M2 = (M+R)/2;
	for(int i = M1+1; i<= M; i++) last = ask(Right[i]);
	solve(L, M1, M, v1);
	for(int i = M+1; i<= M2; i++) last = ask(Right[i]);
	solve(M+1, M2, R, v2);
}

void Solve(int N)
{
	n = N;
	Left.pb(0); Right.pb(0);
	for(int i = 1; i<= 2*N; i++)
	{
		int x = ask(i);
		if(x != last) Left.pb(i);
		else Right.pb(i);
		last = x;
	}
	int M = (1+N)/2;
	for(int i = M+1; i<= N; i++)
	{
		// printf("rem %d\n", Right[i]);
		last = ask(Right[i]);
		// printf("now %d\n", last);
	}
	vector<int> trash;
	for(int i = 0; i<= N; i++) trash.pb(Left[i]);
	solve(1, M, N, trash);
	for(int i = 1; i<= 2*N; i++)
	{
		if(match[i])
		{
			Answer(i, match[i]);
		}
	}
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 10 ms 852 KB Output is correct
5 Correct 18 ms 1216 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Correct 48 ms 2676 KB Output is correct
20 Correct 49 ms 2708 KB Output is correct
21 Correct 37 ms 2568 KB Output is correct
22 Correct 37 ms 2292 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Correct 48 ms 2676 KB Output is correct
20 Correct 49 ms 2708 KB Output is correct
21 Correct 37 ms 2568 KB Output is correct
22 Correct 37 ms 2292 KB Output is correct
23 Correct 53 ms 2692 KB Output is correct
24 Correct 51 ms 2704 KB Output is correct
25 Correct 39 ms 2732 KB Output is correct
26 Correct 39 ms 2428 KB Output is correct

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Correct 48 ms 2676 KB Output is correct
20 Correct 49 ms 2708 KB Output is correct
21 Correct 37 ms 2568 KB Output is correct
22 Correct 37 ms 2292 KB Output is correct
23 Correct 53 ms 2692 KB Output is correct
24 Correct 51 ms 2704 KB Output is correct
25 Correct 39 ms 2732 KB Output is correct
26 Correct 39 ms 2428 KB Output is correct
27 Incorrect 54 ms 2804 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Correct 48 ms 2676 KB Output is correct
20 Correct 49 ms 2708 KB Output is correct
21 Correct 37 ms 2568 KB Output is correct
22 Correct 37 ms 2292 KB Output is correct
23 Correct 53 ms 2692 KB Output is correct
24 Correct 51 ms 2704 KB Output is correct
25 Correct 39 ms 2732 KB Output is correct
26 Correct 39 ms 2428 KB Output is correct
27 Incorrect 54 ms 2804 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 852 KB Output is correct
9 Correct 18 ms 1216 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 12 ms 1000 KB Output is correct
12 Correct 18 ms 1264 KB Output is correct
13 Correct 16 ms 1364 KB Output is correct
14 Correct 15 ms 1088 KB Output is correct
15 Correct 47 ms 2664 KB Output is correct
16 Correct 48 ms 2684 KB Output is correct
17 Correct 37 ms 2576 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Correct 48 ms 2676 KB Output is correct
20 Correct 49 ms 2708 KB Output is correct
21 Correct 37 ms 2568 KB Output is correct
22 Correct 37 ms 2292 KB Output is correct
23 Correct 53 ms 2692 KB Output is correct
24 Correct 51 ms 2704 KB Output is correct
25 Correct 39 ms 2732 KB Output is correct
26 Correct 39 ms 2428 KB Output is correct
27 Incorrect 54 ms 2804 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -