oj.uz

Submission #1006417

# Submission time Handle Problem Language Result Execution time Memory
1006417 2024-06-24T01:57:07 Z AdamGS Minerals (JOI19_minerals) C++17
85 / 100
 1000 ms 3864 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=20000;
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 0 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 600 KB Output is correct
4 Correct 39 ms 1052 KB Output is correct
5 Correct 126 ms 1628 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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 KB Output is correct
19 Correct 851 ms 3664 KB Output is correct
20 Correct 855 ms 3556 KB Output is correct
21 Correct 852 ms 3612 KB Output is correct
22 Correct 834 ms 3328 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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 KB Output is correct
19 Correct 851 ms 3664 KB Output is correct
20 Correct 855 ms 3556 KB Output is correct
21 Correct 852 ms 3612 KB Output is correct
22 Correct 834 ms 3328 KB Output is correct
23 Correct 894 ms 3672 KB Output is correct
24 Correct 858 ms 3612 KB Output is correct
25 Correct 867 ms 3676 KB Output is correct
26 Correct 909 ms 3600 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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 KB Output is correct
19 Correct 851 ms 3664 KB Output is correct
20 Correct 855 ms 3556 KB Output is correct
21 Correct 852 ms 3612 KB Output is correct
22 Correct 834 ms 3328 KB Output is correct
23 Correct 894 ms 3672 KB Output is correct
24 Correct 858 ms 3612 KB Output is correct
25 Correct 867 ms 3676 KB Output is correct
26 Correct 909 ms 3600 KB Output is correct
27 Correct 951 ms 3808 KB Output is correct
28 Correct 925 ms 3856 KB Output is correct
29 Correct 900 ms 3720 KB Output is correct
30 Correct 860 ms 3620 KB Output is correct

Subtask #8
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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 KB Output is correct
19 Correct 851 ms 3664 KB Output is correct
20 Correct 855 ms 3556 KB Output is correct
21 Correct 852 ms 3612 KB Output is correct
22 Correct 834 ms 3328 KB Output is correct
23 Correct 894 ms 3672 KB Output is correct
24 Correct 858 ms 3612 KB Output is correct
25 Correct 867 ms 3676 KB Output is correct
26 Correct 909 ms 3600 KB Output is correct
27 Correct 951 ms 3808 KB Output is correct
28 Correct 925 ms 3856 KB Output is correct
29 Correct 900 ms 3720 KB Output is correct
30 Correct 860 ms 3620 KB Output is correct
31 Execution timed out 1004 ms 3864 KB Time limit exceeded
32 Halted 0 ms 0 KB -

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 0 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 600 KB Output is correct
8 Correct 39 ms 1052 KB Output is correct
9 Correct 126 ms 1628 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 60 ms 1080 KB Output is correct
12 Correct 129 ms 1640 KB Output is correct
13 Correct 127 ms 1612 KB Output is correct
14 Correct 126 ms 1604 KB Output is correct
15 Correct 787 ms 3528 KB Output is correct
16 Correct 806 ms 3408 KB Output is correct
17 Correct 833 ms 3472 KB Output is correct
18 Correct 790 ms 3400 KB Output is correct
19 Correct 851 ms 3664 KB Output is correct
20 Correct 855 ms 3556 KB Output is correct
21 Correct 852 ms 3612 KB Output is correct
22 Correct 834 ms 3328 KB Output is correct
23 Correct 894 ms 3672 KB Output is correct
24 Correct 858 ms 3612 KB Output is correct
25 Correct 867 ms 3676 KB Output is correct
26 Correct 909 ms 3600 KB Output is correct
27 Correct 951 ms 3808 KB Output is correct
28 Correct 925 ms 3856 KB Output is correct
29 Correct 900 ms 3720 KB Output is correct
30 Correct 860 ms 3620 KB Output is correct
31 Execution timed out 1004 ms 3864 KB Time limit exceeded
32 Halted 0 ms 0 KB -