oj.uz

Submission #128793

# Submission time Handle Problem Language Result Execution time Memory
128793 2019-07-11T09:33:29 Z roseanne_pcy Minerals (JOI19_minerals) C++14
70 / 100
 54 ms 2692 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);
		// printf("go %d now %d\n", x, y);
		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])
		{
			// printf("match %d with %d\n", i, match[i]);
			Answer(i, match[i]);
		}
	}
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory 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 760 KB Output is correct
5 Correct 18 ms 1136 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Incorrect 49 ms 2676 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Incorrect 49 ms 2676 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Incorrect 49 ms 2676 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Incorrect 49 ms 2676 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
9 Correct 18 ms 1136 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 13 ms 1000 KB Output is correct
12 Correct 19 ms 1228 KB Output is correct
13 Correct 15 ms 1316 KB Output is correct
14 Correct 15 ms 1216 KB Output is correct
15 Correct 54 ms 2636 KB Output is correct
16 Correct 49 ms 2692 KB Output is correct
17 Correct 37 ms 2616 KB Output is correct
18 Correct 37 ms 2320 KB Output is correct
19 Incorrect 49 ms 2676 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -