oj.uz

Submission #819452

# Submission time Handle Problem Language Result Execution time Memory
819452 2023-08-10T10:54:42 Z AdamGS Minerals (JOI19_minerals) C++17
75 / 100
 31 ms 3804 KB 
#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>T, zapalone;
int czy[LIM], lst=-1;
bool pytaj(int x) {
	int a=Query(x+1);
	swap(a, lst);
	return a!=lst;
}
void dc(int l, int r, vector<pair<int,int>>&V) {
	if(l==r) {
		Answer(T[l]+1, V[0].st+1);
		return;
	}
	int mid=(l+r)/2;
	vector<int>tmp;
	for(auto i : zapalone) {
		if(i<l || i>mid) {
			pytaj(T[i]);
			czy[i]=0;
		} else tmp.pb(i);
	}
	zapalone=tmp;
	for(int i=l; i<=mid; ++i) if(!czy[i]) {
		pytaj(T[i]);
		zapalone.pb(i);
		czy[i]=1;
	}
	vector<pair<int,int>>A, B;
	for(auto i : V) if(i.nd<=mid || !pytaj(i.st)) A.pb(i); else B.pb(i);
	dc(l, mid, A);
	dc(mid+1, r, B);
}
void Solve(int n) {
	vector<int>P;
	rep(i, 2*n) {
		P.pb(i);
		swap(P[i], P[rng()%(i+1)]);
	}
	vector<pair<int,int>>V;
	rep(i, 2*n) {
		if(pytaj(P[i])) T.pb(P[i]);
		else V.pb({P[i], (int)T.size()-1});
	}
	rep(i, T.size()) {
		zapalone.pb(i);
		czy[i]=1;
	}
	dc(0, n-1, V);
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
minerals.cpp:54:2: note: in expansion of macro 'rep'
   54 |  rep(i, T.size()) {
      |  ^~~

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 1 ms 336 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 5 ms 808 KB Output is correct
5 Correct 9 ms 1368 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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 KB Output is correct
19 Correct 31 ms 3740 KB Output is correct
20 Correct 31 ms 3656 KB Output is correct
21 Correct 31 ms 3724 KB Output is correct
22 Correct 30 ms 3576 KB Output is correct

Subtask #6
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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 KB Output is correct
19 Correct 31 ms 3740 KB Output is correct
20 Correct 31 ms 3656 KB Output is correct
21 Correct 31 ms 3724 KB Output is correct
22 Correct 30 ms 3576 KB Output is correct
23 Incorrect 27 ms 3804 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 KB Output is correct
19 Correct 31 ms 3740 KB Output is correct
20 Correct 31 ms 3656 KB Output is correct
21 Correct 31 ms 3724 KB Output is correct
22 Correct 30 ms 3576 KB Output is correct
23 Incorrect 27 ms 3804 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 KB Output is correct
19 Correct 31 ms 3740 KB Output is correct
20 Correct 31 ms 3656 KB Output is correct
21 Correct 31 ms 3724 KB Output is correct
22 Correct 30 ms 3576 KB Output is correct
23 Incorrect 27 ms 3804 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

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 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 9 ms 1368 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 9 ms 1448 KB Output is correct
13 Correct 9 ms 1488 KB Output is correct
14 Correct 9 ms 1488 KB Output is correct
15 Correct 27 ms 3656 KB Output is correct
16 Correct 29 ms 3652 KB Output is correct
17 Correct 27 ms 3748 KB Output is correct
18 Correct 27 ms 3504 KB Output is correct
19 Correct 31 ms 3740 KB Output is correct
20 Correct 31 ms 3656 KB Output is correct
21 Correct 31 ms 3724 KB Output is correct
22 Correct 30 ms 3576 KB Output is correct
23 Incorrect 27 ms 3804 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -