oj.uz

Submission #819706

# Submission time Handle Problem Language Result Execution time Memory
819706 2023-08-10T12:45:36 Z AdamGS Minerals (JOI19_minerals) C++17
90 / 100
 419 ms 3608 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=2000;
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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 5 ms 464 KB Output is correct
3 Correct 19 ms 628 KB Output is correct
4 Correct 56 ms 904 KB Output is correct
5 Correct 133 ms 1468 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct
19 Correct 389 ms 3392 KB Output is correct
20 Correct 390 ms 3328 KB Output is correct
21 Correct 387 ms 3412 KB Output is correct
22 Correct 379 ms 3216 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct
19 Correct 389 ms 3392 KB Output is correct
20 Correct 390 ms 3328 KB Output is correct
21 Correct 387 ms 3412 KB Output is correct
22 Correct 379 ms 3216 KB Output is correct
23 Correct 393 ms 3400 KB Output is correct
24 Correct 408 ms 3412 KB Output is correct
25 Correct 399 ms 3436 KB Output is correct
26 Correct 398 ms 3256 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct
19 Correct 389 ms 3392 KB Output is correct
20 Correct 390 ms 3328 KB Output is correct
21 Correct 387 ms 3412 KB Output is correct
22 Correct 379 ms 3216 KB Output is correct
23 Correct 393 ms 3400 KB Output is correct
24 Correct 408 ms 3412 KB Output is correct
25 Correct 399 ms 3436 KB Output is correct
26 Correct 398 ms 3256 KB Output is correct
27 Correct 408 ms 3432 KB Output is correct
28 Correct 410 ms 3508 KB Output is correct
29 Correct 402 ms 3456 KB Output is correct
30 Correct 395 ms 3368 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct
19 Correct 389 ms 3392 KB Output is correct
20 Correct 390 ms 3328 KB Output is correct
21 Correct 387 ms 3412 KB Output is correct
22 Correct 379 ms 3216 KB Output is correct
23 Correct 393 ms 3400 KB Output is correct
24 Correct 408 ms 3412 KB Output is correct
25 Correct 399 ms 3436 KB Output is correct
26 Correct 398 ms 3256 KB Output is correct
27 Correct 408 ms 3432 KB Output is correct
28 Correct 410 ms 3508 KB Output is correct
29 Correct 402 ms 3456 KB Output is correct
30 Correct 395 ms 3368 KB Output is correct
31 Correct 411 ms 3528 KB Output is correct
32 Correct 418 ms 3600 KB Output is correct
33 Correct 409 ms 3580 KB Output is correct
34 Correct 416 ms 3556 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 5 ms 464 KB Output is correct
7 Correct 19 ms 628 KB Output is correct
8 Correct 56 ms 904 KB Output is correct
9 Correct 133 ms 1468 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 80 ms 1192 KB Output is correct
12 Correct 132 ms 1520 KB Output is correct
13 Correct 136 ms 1524 KB Output is correct
14 Correct 131 ms 1476 KB Output is correct
15 Correct 383 ms 3292 KB Output is correct
16 Correct 377 ms 3324 KB Output is correct
17 Correct 372 ms 3268 KB Output is correct
18 Correct 369 ms 3172 KB Output is correct
19 Correct 389 ms 3392 KB Output is correct
20 Correct 390 ms 3328 KB Output is correct
21 Correct 387 ms 3412 KB Output is correct
22 Correct 379 ms 3216 KB Output is correct
23 Correct 393 ms 3400 KB Output is correct
24 Correct 408 ms 3412 KB Output is correct
25 Correct 399 ms 3436 KB Output is correct
26 Correct 398 ms 3256 KB Output is correct
27 Correct 408 ms 3432 KB Output is correct
28 Correct 410 ms 3508 KB Output is correct
29 Correct 402 ms 3456 KB Output is correct
30 Correct 395 ms 3368 KB Output is correct
31 Correct 411 ms 3528 KB Output is correct
32 Correct 418 ms 3600 KB Output is correct
33 Correct 409 ms 3580 KB Output is correct
34 Correct 416 ms 3556 KB Output is correct
35 Incorrect 419 ms 3608 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -