Submission #376706

#	Time	Username	Problem	Language	Result	Execution time	Memory
376706		fhvirus	Minerals (JOI19_minerals)	C++17	80 / 100	46 ms	2816 KiB

minerals

#include "minerals.h"
 
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr<<endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr<<*a<<" \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
 
void solve(vector<int> &a, vector<int> &b, bool in){
	assert(a.size() == b.size());
	debug("solving:");
	DE(AI(a)); DE(AI(b));
 
	if(a.size() < 1 or b.size() < 1){
		return;
	}
	if(a.size() == 1 and b.size() == 1){
		Answer(a[0], b[0]);
		return;
	}
	vector<int> la, lb, ra, rb;
	int h = 1<<(__lg(a.size()) - 1);
	for(int i = 0; i < h; ++i) la.pb(a[i]);
	for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
 
	int ls, cs;
	for(int i: la) cs = Query(i);
 
	for(int i: b){
		ls = cs;
		cs = Query(i);
		if(cs == ls ^ in) ra.pb(i);
		else rb.pb(i);
	}
	// for(int i: rb)
	// 	cs = Query(i);
 
	DE(AI(la)); DE(AI(lb));
	DE(AI(ra)); DE(AI(rb));
 
	solve(la, ra, !in);
	solve(lb, rb,  in);
}
 
void Solve(int N) {
	vector<int> a, b;
	int ls = 0, cs;
	for(int i = 1; i <= N * 2; ++i){
		cs = Query(i);
		if(cs == ls) b.pb(i);
		else a.pb(i);
		ls = cs;
	}
 	solve(a, b, true);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
minerals.cpp:28:2: note: in expansion of macro 'debug'
   28 |  debug("solving:");
      |  ^~~~~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:29:2: note: in expansion of macro 'DE'
   29 |  DE(AI(a)); DE(AI(b));
      |  ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:29:13: note: in expansion of macro 'DE'
   29 |  DE(AI(a)); DE(AI(b));
      |             ^~
minerals.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
      |                 ~~^~~~~~~~~~
minerals.cpp:49:9: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   49 |   if(cs == ls ^ in) ra.pb(i);
      |      ~~~^~~~~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:55:2: note: in expansion of macro 'DE'
   55 |  DE(AI(la)); DE(AI(lb));
      |  ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:55:14: note: in expansion of macro 'DE'
   55 |  DE(AI(la)); DE(AI(lb));
      |              ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:56:2: note: in expansion of macro 'DE'
   56 |  DE(AI(ra)); DE(AI(rb));
      |  ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:56:14: note: in expansion of macro 'DE'
   56 |  DE(AI(ra)); DE(AI(rb));
      |              ^~
minerals.cpp:49:9: warning: 'cs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   if(cs == ls ^ in) ra.pb(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