oj.uz

Submission #262074

# Submission time Handle Problem Language Result Execution time Memory
262074 2020-08-12T10:27:10 Z patrikpavic2 Minerals (JOI19_minerals) C++17
75 / 100
 164 ms 55316 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], izb[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, int zad){
	if(l == r) return;
	mks = max(mks, raz);
	int rez = (l + r) / 2;
	if(zad){
		while(rez < r && ((rez - l + 1) & (rez - l)) != 0)
			rez++;
	}
	else{
		while(rez >= l && ((r - rez) & (r - rez - 1)) != 0)		
			rez--;
	}
	for(int i = l;i <= rez;i++)
		kod[i] += (1 << raz);
	pripremi(l, rez, raz + 1, 0);
	pripremi(rez + 1, r, raz + 1, 1);
}

void odradi(int red){
	for(int i = 1;i <= 2 * n;i++){
		if(!izb[i] && !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 = 2 * n;i >= 1;i--){
		if(!tp[i] || ans[i]) continue;
		while(izb[kol[red][P[i]].back()]) kol[red][P[i]].pop_back();
		if(kol[red][P[i]].size() == 1 || (kol[red][P[i]][(int)kol[red][P[i]].size() - 2] < i)){
			ans[i] = *lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i);
			izb[ans[i]] = 1;
		}
	}
	for(int i = 1;i <= 2 * n;i++){
		if(!tp[i] || ans[i]) continue;
		while(izb[kol[red][P[i]].back()]) kol[red][P[i]].pop_back();
		if(kol[red][P[i]].size() == 1 || (kol[red][P[i]][(int)kol[red][P[i]].size() - 2] < i)){
			ans[i] = kol[red][P[i]].back();
			izb[ans[i]] = 1;
		}
	}		
	
}

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

void Solve(int nn) {
	n = nn; 
	pripremi(0, n - 1, 0, 1);
	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); mozda(0); mozda(0);
	for(int i = 0;i <= mks;i++){
		odradi(i);
		mozda(i + 1); mozda(i + 1); 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 47616 KB Output is correct
2 Correct 31 ms 47616 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 32 ms 47736 KB Output is correct
2 Correct 35 ms 47864 KB Output is correct
3 Correct 38 ms 48248 KB Output is correct
4 Correct 45 ms 48892 KB Output is correct
5 Correct 60 ms 50168 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct
19 Correct 164 ms 55284 KB Output is correct
20 Correct 156 ms 55284 KB Output is correct
21 Correct 104 ms 55316 KB Output is correct
22 Correct 114 ms 54772 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct
19 Correct 164 ms 55284 KB Output is correct
20 Correct 156 ms 55284 KB Output is correct
21 Correct 104 ms 55316 KB Output is correct
22 Correct 114 ms 54772 KB Output is correct
23 Incorrect 152 ms 54960 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 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct
19 Correct 164 ms 55284 KB Output is correct
20 Correct 156 ms 55284 KB Output is correct
21 Correct 104 ms 55316 KB Output is correct
22 Correct 114 ms 54772 KB Output is correct
23 Incorrect 152 ms 54960 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 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct
19 Correct 164 ms 55284 KB Output is correct
20 Correct 156 ms 55284 KB Output is correct
21 Correct 104 ms 55316 KB Output is correct
22 Correct 114 ms 54772 KB Output is correct
23 Incorrect 152 ms 54960 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 47616 KB Output is correct
2 Correct 31 ms 47616 KB Output is correct
3 Correct 32 ms 47616 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 32 ms 47736 KB Output is correct
6 Correct 35 ms 47864 KB Output is correct
7 Correct 38 ms 48248 KB Output is correct
8 Correct 45 ms 48892 KB Output is correct
9 Correct 60 ms 50168 KB Output is correct
10 Correct 35 ms 47736 KB Output is correct
11 Correct 57 ms 49400 KB Output is correct
12 Correct 72 ms 50300 KB Output is correct
13 Correct 51 ms 50296 KB Output is correct
14 Correct 58 ms 50168 KB Output is correct
15 Correct 148 ms 55028 KB Output is correct
16 Correct 141 ms 55028 KB Output is correct
17 Correct 93 ms 55028 KB Output is correct
18 Correct 116 ms 54644 KB Output is correct
19 Correct 164 ms 55284 KB Output is correct
20 Correct 156 ms 55284 KB Output is correct
21 Correct 104 ms 55316 KB Output is correct
22 Correct 114 ms 54772 KB Output is correct
23 Incorrect 152 ms 54960 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -