Submission #129048

#	Time	Username	Problem	Language	Result	Execution time	Memory
129048		sealnot123	Minerals (JOI19_minerals)	C++14	70 / 100	72 ms	18680 KiB

minerals

#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 (stderr)

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 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10