Submission #112586

#	Time	Username	Problem	Language	Result	Execution time	Memory
112586		reality	Minerals (JOI19_minerals)	C++17	40 / 100	38 ms	3444 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 was[N];

void Go(vi a,vi b) {
	if (a.size() == 1) {
		Answer(a[0],b[0]);
	} else {
		int sz = a.size();
		int m = sz / 2;
		int cnt;
		for (int i = 0;i < m;++i)
			cnt = Query(a[i]),was[a[i]] ^= 1;
		vi x1(a.begin(),a.begin() + m),y1,x2(a.begin() + m,a.end()),y2;
		int h = was[a[0]];
		for (int i = 0;i < sz;++i) {
			if (h) {
				int cur = Query(b[i]);
				was[b[i]] ^= 1;
				if (cnt + 1 == cur) {
					y2.pb(b[i]);
					Query(b[i]);
					was[b[i]] ^= 1;
				} else {
					y1.pb(b[i]);
				}
			} else {
				int cur = Query(b[i]);
				was[b[i]] ^= 1;
				if (cnt == cur) {
					y2.pb(b[i]);
					Query(b[i]);
					was[b[i]] ^= 1;
				} else {
					y1.pb(b[i]);
					cnt = cur;
				}
			}
		}
		Go(x1,y1);
		Go(x2,y2);
	}
}

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

Compilation message (stderr)

minerals.cpp: In function 'void Go(std::vector<int>, std::vector<int>)':
minerals.cpp:50:5: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (cnt == cur) {
     ^~

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