oj.uz

Submission #129048

# Submission time Handle Problem Language Result Execution time Memory
129048 2019-07-11T13:21:33 Z sealnot123 Minerals (JOI19_minerals) C++14
70 / 100
 72 ms 18680 KB 
#include "minerals.h"

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 43005;
vector<int> L[4*N], R[4*N];
int mineral[2*N];

void play(int t, int now, int n, vector<int> &l, vector<int> &r){
	int last, a, i;
	/*printf("n = %d\n",n);
	for(i=0;i<n;i++) printf("%d ",l[i]);
	printf("|| ");
	for(i=0;i<n;i++) printf("%d ",r[i]);
	printf("=================\n");*/
	/*printf("%d %d %d\n",n,SZ(l),SZ(r));*/
	assert(n == SZ(l));
	if(n == 1){
		Answer(l[0], r[0]);
		l.clear(); r.clear();
		return ;
	}
	if(n == 2){
		if(t==0){
			last = Query(r[0]);
			a = Query(l[0]);
			if(a == last){
				Answer(l[0], r[0]);
				Answer(l[1], r[1]);
			}else{
				Answer(l[0], r[1]);
				Answer(l[1], r[0]);
			}
		}else if(t==1){
			last = Query(r[0]);
			a = Query(l[0]);
			if(a == last){
				Answer(l[0], r[1]);
				Answer(l[1], r[0]);
			}else{
				Answer(l[0], r[0]);
				Answer(l[1], r[1]);
			}
		}else if(t==2){
			last = Query(l[1]);
			a = Query(r[1]);
			if(a == last){
				Answer(l[0], r[1]);
				Answer(l[1], r[0]);
			}else{
				Answer(l[0], r[0]);
				Answer(l[1], r[1]);
			}
		}
		return ;
	}
	
		for(i = 0; i < n/2; i++){
			last = Query(r[i]);
			R[now<<1].pb(r[i]);
		}
		for(i = n/2; i < n; i++) R[now<<1|1].pb(r[i]);
	for(i = 0; i < n; i++){
		a = Query(l[i]);
		if(t==0){
			if(a != last) L[now<<1|1].pb(l[i]);
			else L[now<<1].pb(l[i]); 	
		}else{	
			if(a != last) L[now<<1].pb(l[i]);
			else L[now<<1|1].pb(l[i]); 
		}
		last = a;
	}
	if(t == 2){
		play(1, now<<1|1, n-n/2, L[now<<1|1], R[now<<1|1]);
		play(0, now<<1, n/2, L[now<<1], R[now<<1]);
	}else if(t == 0){
		play(2, now<<1, n/2, L[now<<1], R[now<<1]);
		play(1, now<<1|1, n-n/2, R[now<<1|1], L[now<<1|1]);
	}else{
		play(1, now<<1, n/2, R[now<<1], L[now<<1]);
		play(2, now<<1|1, n-n/2, L[now<<1|1], R[now<<1|1]);
	}
	l.clear(); r.clear();
}

void Solve(int n) {
  	int last = 0, now = 2*n;
  	int i,j,k,l,a,b,c,d;
  	for(i = 1; i <= 2*n; i++) mineral[i] = i;
  	for(i = 1; i <= n; i++){
  		a = Query(mineral[i]);
  		/*if(i<=2) printf("%d : %d\n",i,a);*/
  		if(a == last) a = Query(mineral[i]),swap(mineral[i], mineral[now--]), i--;
  		last = a;
  	}
  	/*printf("%d\n",now);*/
  	for(i = 1; i <= n; i++) Query(mineral[i]);
  	for(i = 1; i <= n; i++) L[1].pb(mineral[i]), R[1].pb(mineral[i+n]);
  	play(0, 1, n, L[1], R[1]);
  	return ;
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:100:10: warning: unused variable 'j' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
          ^
minerals.cpp:100:12: warning: unused variable 'k' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
            ^
minerals.cpp:100:14: warning: unused variable 'l' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
              ^
minerals.cpp:100:18: warning: unused variable 'b' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
                  ^
minerals.cpp:100:20: warning: unused variable 'c' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
                    ^
minerals.cpp:100:22: warning: unused variable 'd' [-Wunused-variable]
    int i,j,k,l,a,b,c,d;
                      ^
minerals.cpp: In function 'void play(int, int, int, std::vector<int>&, std::vector<int>&)':
minerals.cpp:77:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(a != last) L[now<<1|1].pb(l[i]);
    ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 11 ms 8824 KB Output is correct
3 Correct 14 ms 9088 KB Output is correct
4 Correct 18 ms 9848 KB Output is correct
5 Correct 29 ms 11432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct
19 Incorrect 71 ms 18444 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct
19 Incorrect 71 ms 18444 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct
19 Incorrect 71 ms 18444 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct
19 Incorrect 71 ms 18444 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8444 KB Output is correct
3 Correct 9 ms 8516 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 11 ms 8824 KB Output is correct
7 Correct 14 ms 9088 KB Output is correct
8 Correct 18 ms 9848 KB Output is correct
9 Correct 29 ms 11432 KB Output is correct
10 Correct 10 ms 8516 KB Output is correct
11 Correct 24 ms 10764 KB Output is correct
12 Correct 32 ms 11352 KB Output is correct
13 Correct 28 ms 11320 KB Output is correct
14 Correct 25 ms 11260 KB Output is correct
15 Correct 72 ms 18680 KB Output is correct
16 Correct 71 ms 18532 KB Output is correct
17 Correct 58 ms 18420 KB Output is correct
18 Correct 58 ms 18272 KB Output is correct
19 Incorrect 71 ms 18444 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -