Submission #112608

#	Time	Username	Problem	Language	Result	Execution time	Memory
112608		reality	Minerals (JOI19_minerals)	C++17	100 / 100	63 ms	3540 KiB

minerals

#include "minerals.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int N = 1e5 + 5;

int cnt;

void Go(vi a,vi b,int ok) {
	random_shuffle(all(b));
	if (a.size() == 1) {
		Answer(a[0],b[0]);
	} else {
		int sz = a.size();
		int m = ceil(0.36 * sz);
		if (ok) {
			m = sz - m;
			for (int i = m;i < sz;++i)
				cnt = Query(a[i]);
		} else {
			for (int i = 0;i < m;++i)
				cnt = Query(a[i]);
		}
		vi x,y;
		for (auto it : b) {
			if (x.size() == m) {
				y.pb(it);
				continue;
			} else
			if (y.size() == sz - m) {
				x.pb(it);
				continue;
			}
			int cur = Query(it);
			if (cnt != cur) {
				y.pb(it);
			} else {
				x.pb(it);
			}
			cnt = cur;
		}
		Go(vi(a.begin(),a.begin() + m),x,1);
		Go(vi(a.begin() + m,a.end()),y,0);
	}
}

void Solve(int N) {
	srand(time(0));
  	vi a,b;
  	for (int i = 1;i <= 2 * N;++i) {
  		int cur = Query(i);
  		if (cnt != cur) {
  			a.pb(i);
  		} else {
  			b.pb(i);
  		}
  		cnt = cur;
  	}
  	Go(a,b,1);
}

Compilation message (stderr)

minerals.cpp: In function 'void Go(std::vector<int>, std::vector<int>, int)':
minerals.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (x.size() == m) {
        ~~~~~~~~~^~~~
minerals.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (y.size() == sz - m) {
        ~~~~~~~~~^~~~~~~~~

• 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