Submission #376696

#	Time	Username	Problem	Language	Result	Execution time	Memory
376696		fhvirus	Minerals (JOI19_minerals)	C++17	40 / 100	32 ms	2540 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){
	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 = a.size() / 2;
	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);
	assert(cs == la.size());
 
	for(int i: b){
		ls = cs;
		cs = Query(i);
		if(cs == ls) ra.pb(i);
		else rb.pb(i);
	}
	for(int i: b)
		cs = Query(i);
 
	DE(AI(la)); DE(AI(lb));
	DE(AI(ra)); DE(AI(rb));
 
	for(int i: la) Query(i);
 
	solve(la, ra);
	solve(lb, rb);
}
 
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;
	}
	for(int i = 1; i <= N * 2; ++i)
		Query(i);
 	solve(a, b);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&)':
minerals.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
minerals.cpp:27:2: note: in expansion of macro 'debug'
   27 |  debug("solving:");
      |  ^~~~~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:28:2: note: in expansion of macro 'DE'
   28 |  DE(AI(a)); DE(AI(b));
      |  ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
   23 | #define DE(...) 0
      |                 ^
minerals.cpp:28:13: note: in expansion of macro 'DE'
   28 |  DE(AI(a)); DE(AI(b));
      |             ^~
minerals.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
      |                 ~~^~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from minerals.cpp:4:
minerals.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  assert(cs == la.size());
      |         ~~~^~~~~~~~~~~~
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:44:9: warning: 'cs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |  assert(cs == la.size());
      |         ^~

• 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