oj.uz

Submission #1006389

# Submission time Handle Problem Language Result Execution time Memory
1006389 2024-06-24T00:23:30 Z AdamGS Minerals (JOI19_minerals) C++17
90 / 100
 295 ms 3812 KB 
#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7, INF=1e9+7, C=3000;
int czy[2*LIM], lst=-1;
pair<int,int>dp[LIM];
bool pytaj(int x) {
	czy[x]^=1;
	int a=Query(x+1);
	swap(a, lst);
	return a!=lst;
}
void dc(vector<int>&X, vector<int>&Y) {
	if(X.size()==1) {
		Answer(X[0]+1, Y[0]+1);
		return;
	}
	if(X.size()==2) {
		pytaj(X[0]);
		if(czy[X[0]]) swap(X[0], X[1]);
		if(!pytaj(Y[0])) swap(Y[0], Y[1]);
		Answer(X[0]+1, Y[0]+1);
		Answer(X[1]+1, Y[1]+1);
		return;
	}
	vector<int>AX, AY, BX, BY;
	rep(i, dp[X.size()].nd) {
		pytaj(X[i]);
		AX.pb(X[i]);
	}
	for(int i=dp[X.size()].nd; i<X.size(); ++i) BX.pb(X[i]);
	for(auto i : Y) if(czy[X[0]]==pytaj(i)) BY.pb(i); else AY.pb(i);
	dc(AX, AY);
	dc(BX, BY);
}
void Solve(int n) {
	dp[2]={2, 0};
	for(int i=3; i<=n; ++i) {
		dp[i]={INF, INF};
		for(int k=max(i/2-C, 1); k<min(i, i/2+C); ++k) dp[i]=min(dp[i], {i+k+dp[k].st+dp[i-k].st, k});
	}
	vector<int>X, Y;
	rep(i, 2*n) {
		if(pytaj(i)) X.pb(i);
		else Y.pb(i);
	}
	dc(X, Y);
}

Compilation message

minerals.cpp: In function 'void dc(std::vector<int>&, std::vector<int>&)':
minerals.cpp:36:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=dp[X.size()].nd; i<X.size(); ++i) BX.pb(X[i]);
      |                             ~^~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 11 ms 756 KB Output is correct
4 Correct 36 ms 1056 KB Output is correct
5 Correct 87 ms 1612 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct
19 Correct 279 ms 3540 KB Output is correct
20 Correct 245 ms 3408 KB Output is correct
21 Correct 256 ms 3472 KB Output is correct
22 Correct 245 ms 3236 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct
19 Correct 279 ms 3540 KB Output is correct
20 Correct 245 ms 3408 KB Output is correct
21 Correct 256 ms 3472 KB Output is correct
22 Correct 245 ms 3236 KB Output is correct
23 Correct 266 ms 3452 KB Output is correct
24 Correct 265 ms 3536 KB Output is correct
25 Correct 270 ms 3588 KB Output is correct
26 Correct 257 ms 3292 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct
19 Correct 279 ms 3540 KB Output is correct
20 Correct 245 ms 3408 KB Output is correct
21 Correct 256 ms 3472 KB Output is correct
22 Correct 245 ms 3236 KB Output is correct
23 Correct 266 ms 3452 KB Output is correct
24 Correct 265 ms 3536 KB Output is correct
25 Correct 270 ms 3588 KB Output is correct
26 Correct 257 ms 3292 KB Output is correct
27 Correct 264 ms 3556 KB Output is correct
28 Correct 283 ms 3788 KB Output is correct
29 Correct 262 ms 3680 KB Output is correct
30 Correct 264 ms 3604 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct
19 Correct 279 ms 3540 KB Output is correct
20 Correct 245 ms 3408 KB Output is correct
21 Correct 256 ms 3472 KB Output is correct
22 Correct 245 ms 3236 KB Output is correct
23 Correct 266 ms 3452 KB Output is correct
24 Correct 265 ms 3536 KB Output is correct
25 Correct 270 ms 3588 KB Output is correct
26 Correct 257 ms 3292 KB Output is correct
27 Correct 264 ms 3556 KB Output is correct
28 Correct 283 ms 3788 KB Output is correct
29 Correct 262 ms 3680 KB Output is correct
30 Correct 264 ms 3604 KB Output is correct
31 Correct 277 ms 3812 KB Output is correct
32 Correct 277 ms 3808 KB Output is correct
33 Correct 295 ms 3788 KB Output is correct
34 Correct 265 ms 3528 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 11 ms 756 KB Output is correct
8 Correct 36 ms 1056 KB Output is correct
9 Correct 87 ms 1612 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 90 ms 1592 KB Output is correct
13 Correct 84 ms 1632 KB Output is correct
14 Correct 85 ms 1612 KB Output is correct
15 Correct 231 ms 3428 KB Output is correct
16 Correct 245 ms 3408 KB Output is correct
17 Correct 236 ms 3268 KB Output is correct
18 Correct 257 ms 3152 KB Output is correct
19 Correct 279 ms 3540 KB Output is correct
20 Correct 245 ms 3408 KB Output is correct
21 Correct 256 ms 3472 KB Output is correct
22 Correct 245 ms 3236 KB Output is correct
23 Correct 266 ms 3452 KB Output is correct
24 Correct 265 ms 3536 KB Output is correct
25 Correct 270 ms 3588 KB Output is correct
26 Correct 257 ms 3292 KB Output is correct
27 Correct 264 ms 3556 KB Output is correct
28 Correct 283 ms 3788 KB Output is correct
29 Correct 262 ms 3680 KB Output is correct
30 Correct 264 ms 3604 KB Output is correct
31 Correct 277 ms 3812 KB Output is correct
32 Correct 277 ms 3808 KB Output is correct
33 Correct 295 ms 3788 KB Output is correct
34 Correct 265 ms 3528 KB Output is correct
35 Incorrect 271 ms 3772 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -