Submission #1020128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020128		Baytoro	Minerals (JOI19_minerals)	C++17	100 / 100	33 ms	4812 KiB

minerals

#include <cstdio>
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <cmath>

#define pb push_back
using namespace std;
//--------------------------------------------------------------------//
// Do not change this part of the code
/*#ifdef ONLINE_JUDGE
int Query(int x) {
    cout << "q " << x << endl; fflush(stdout);
    int res; fflush(stdin); cin >> res;
    return res;
}
void Answer(int a, int b) {
    cout << "a " << a << " " << b << endl; fflush(stdout);
}
#else*/
// But this part can be changed
#include "minerals.h"
//#include "grader.cpp"
/*int Query(int x) {
    return Query(x);
}
void Answer(int a, int b) {
    return Answer(a, b);
}*/
//#endif
//--------------------------------------------------------------------//
vector<int> used(1e5+5);

int pre=0;
void calc(vector<int> a, vector<int> b, int col){
	if(a.size()==0) return;
	if(a.size()==1){
		if(used[a[0]]) return;
		Answer(a[0],b[0]);
		used[a[0]]=used[b[0]]=1;
		return;
	}
	int k=(0.381*a.size());
	vector<int> f,A,s,B;
	for(int i=0;i<=k;i++) {
		f.pb(a[i]);
		pre=Query(a[i]);
		
	}
	for(int i=k+1;i<a.size();i++)
		s.pb(a[i]);
	for(int i=0;i<b.size();i++){
		if(f.size()==A.size()){
			B.pb(b[i]);
			continue;
		}
		else if(s.size()==B.size()){
			A.pb(b[i]);
			continue;
		}
		int tmp=Query(b[i]);
		if((tmp!=pre)==col) A.pb(b[i]);
		else B.pb(b[i]);
		pre=tmp;
	}
	calc(f,A,col^1);
	calc(s,B,col);
}
void Solve(int n) {
	vector<int> a(2*n+1);
	int last=0;
	vector<int> f,s;
	for(int i=1;i<=2*n;i++){
		int t=Query(i);
		if(t!=last) f.pb(i);
		else s.pb(i);
		last=t;
		pre=t;
	}
	calc(f,s,1);
}
/*
4 
1 5
2 6
3 4
7 8
*/


//--------------------------------------------------------------------//
// Do not change this part of the code
/*#ifdef ONLINE_JUDGE
int main() {
    int N; fflush(stdin); cin >> N;
    Solve(N);
    cout << "f" << endl; fflush(stdout);
}
#endif*/
//--------------------------------------------------------------------//

Compilation message (stderr)

minerals.cpp: In function 'void calc(std::vector<int>, std::vector<int>, int)':
minerals.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=k+1;i<a.size();i++)
      |                ~^~~~~~~~~
minerals.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i=0;i<b.size();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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10