oj.uz

Submission #262057

# Submission time Handle Problem Language Result Execution time Memory
262057 2020-08-12T10:15:33 Z patrikpavic2 Minerals (JOI19_minerals) C++17
75 / 100
 128 ms 56436 KB 
#include "minerals.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 1e5 + 500;

int kod[N], tp[N], P[N], ans[N];
int un[N], lst = 0, mks = 0, n;
vector < int > kol[20][N];

int pitaj(int x){
	int nw = Query(x);
	int ret = abs(lst - nw);
	lst = nw; un[x] = !un[x];
	return ret;
}

void pripremi(int l, int r, int raz){
	if(l == r) return;
	mks = max(mks, raz);
	for(int i = l;i <= (l + r) / 2;i++)
		kod[i] += (1 << raz);
	pripremi(l, (l + r) / 2, raz + 1);
	pripremi((l + r) / 2 + 1, r, raz + 1);
}

void odradi(int red){
	for(int i = 1;i <= 2 * n;i++){
		if(!tp[i] && (un[i] ^ (!!(P[i] & (1 << red)))))
			pitaj(i);
	}
	for(int i = 1;i <= 2 * n;i++)
		if(tp[i] && !ans[i]){
			int odg = !pitaj(i);
			P[i] += odg * (1 << red);
		}
}

inline void mozda(int red){
	for(int i = 1;i <= 2 * n;i++){
		if(!tp[i] || ans[i]) continue;
		//printf("i = %d P[i] = %d kol = %d\n", i, P[i], (int)kol[red][P[i]].size());
		if(lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i) + 1 == kol[red][P[i]].end()){
			ans[i] = *lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i);
		//	printf("nasao\n");
		}
	}	
	
}

bool cmp(int x, int y){
	return P[x] < P[y];
}

void Solve(int nn) {
	n = nn; 
	pripremi(0, n - 1, 0);
	int cur = 0;
	for(int i = 1;i <= 2 * n;i++){
		tp[i] = pitaj(i);
		if(!tp[i]){
			P[i] = kod[cur++];
			for(int j = 0;j <= mks + 1;j++)
				kol[j][P[i] & ((1 << j) - 1)].PB(i);
		}
	}
	mozda(0);
	for(int i = 0;i <= mks;i++){
		odradi(i);
		mozda(i + 1);
	}
	for(int i = 1;i <= 2 * n;i++){
		//if(tp[i]) printf("%d %d\n", i, ans[i]);
		if(tp[i]) Answer(i, ans[i]);
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47736 KB Output is correct
2 Correct 35 ms 47868 KB Output is correct
3 Correct 36 ms 48120 KB Output is correct
4 Correct 42 ms 48896 KB Output is correct
5 Correct 53 ms 50172 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct
19 Correct 126 ms 56340 KB Output is correct
20 Correct 127 ms 56436 KB Output is correct
21 Correct 111 ms 56436 KB Output is correct
22 Correct 103 ms 56152 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct
19 Correct 126 ms 56340 KB Output is correct
20 Correct 127 ms 56436 KB Output is correct
21 Correct 111 ms 56436 KB Output is correct
22 Correct 103 ms 56152 KB Output is correct
23 Incorrect 126 ms 56192 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct
19 Correct 126 ms 56340 KB Output is correct
20 Correct 127 ms 56436 KB Output is correct
21 Correct 111 ms 56436 KB Output is correct
22 Correct 103 ms 56152 KB Output is correct
23 Incorrect 126 ms 56192 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct
19 Correct 126 ms 56340 KB Output is correct
20 Correct 127 ms 56436 KB Output is correct
21 Correct 111 ms 56436 KB Output is correct
22 Correct 103 ms 56152 KB Output is correct
23 Incorrect 126 ms 56192 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct
2 Correct 33 ms 47480 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 33 ms 47736 KB Output is correct
6 Correct 35 ms 47868 KB Output is correct
7 Correct 36 ms 48120 KB Output is correct
8 Correct 42 ms 48896 KB Output is correct
9 Correct 53 ms 50172 KB Output is correct
10 Correct 33 ms 47736 KB Output is correct
11 Correct 51 ms 49656 KB Output is correct
12 Correct 58 ms 50296 KB Output is correct
13 Correct 56 ms 50296 KB Output is correct
14 Correct 51 ms 50168 KB Output is correct
15 Correct 120 ms 56436 KB Output is correct
16 Correct 128 ms 56392 KB Output is correct
17 Correct 117 ms 56308 KB Output is correct
18 Correct 112 ms 55924 KB Output is correct
19 Correct 126 ms 56340 KB Output is correct
20 Correct 127 ms 56436 KB Output is correct
21 Correct 111 ms 56436 KB Output is correct
22 Correct 103 ms 56152 KB Output is correct
23 Incorrect 126 ms 56192 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -