Submission #517106

#	Time	Username	Problem	Language	Result	Execution time	Memory
517106		lovrot	Minerals (JOI19_minerals)	C++14	80 / 100	52 ms	3388 KiB

minerals

#include <bits/stdc++.h> 
#include "minerals.h"

#define pb push_back
#define vec vector
#define siz size()
using namespace std;

int n;	
int pref; 

/*
int query_ans;
bool on[100000];
map<int, int> ans_esp;
int Query(int x){
	int y = ans_esp[x]; 
		
	if(!on[x]){ 
		if(!on[y])
			query_ans++;
		on[x] = 1;
	}
	else{ 
		if(!on[y])
			query_ans--;
		on[x] = 0;
	}	
	return query_ans;
}
void Answer(int x, int y){ 
	if(ans_esp[x] == y)
		return;
	cout << "FAIL\n";
	exit(0);
} */

bool query(int x){ 
	int now = Query(x);
	bool ret = (now != pref);
	pref = now;
	return ret;
}

void solve(vec<int> x, vec<int> y, bool all_in){ 
	if(x.siz == 1){ 
		//cout << x[0] << " " << y[0] << "\n";
		Answer(x[0], y[0]);
		return;
	}

	vec<int> lx, rx;
	vec<int> ly, ry;
	int m = x.siz / 2;

	if(all_in){ 
		for(int i = 0; i < x.siz; i++){ 
			if(i < m){ 
				query(x[i]);		
				lx.pb(x[i]);				
			} else{ 
				rx.pb(x[i]);
			}
		}
	} else{ 
		for(int i = 0; i < x.siz; i++){ 
			if(i < m){ 
				query(x[i]);
				rx.pb(x[i]);
			} else
				lx.pb(x[i]);
		}
	}

	for(int i : y){ 
		if(query(i)) ly.pb(i);
		else  ry.pb(i);
	}
	/*
	for(int i : x)
		cout << i << " ";
	cout << "\n";
	for(int i : y)
		cout << i << " ";
	cout << "\n----------\n";
	*/
	solve(lx, ly, 0); 
	solve(rx, ry, 1);
}

void Solve(int N){ 
	n = N;

	vec<int> a;
	vec<int> b;

	for(int i = 1; i <= n * 2; i++){ 
		if(query(i)) a.pb(i);
		else b.pb(i);
	}

	solve(a, b, 1);
}

/*
int main(){ 	
	ios_base::sync_with_stdio(0);

	int n;

	cin >> n;

	for(int i = 0; i < n; i++){ 
		int x, y;
		cin >> x >> y;
		ans_esp[x] = y;
		ans_esp[y] = x;
	}

	Solve(n);

	cout << "Correct\n";

	return 0;
}*/

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < x.siz; i++){
      |                    ^
minerals.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i = 0; i < x.siz; i++){
      |                    ^

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10