제출 #530324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530324		fhvirus	Minerals (JOI19_minerals)	C++17	85 / 100	441 ms	6448 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;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

void solve(vector<int> &a, vector<int> &b, bool in){
	debug("solving:", a, b);
	assert(a.size() == b.size());
	int n = a.size();

	if(n < 1) return;
	if(n == 1){
		Answer(a[0], b[0]);
		return;
	}

	vector<int> la, lb, ra, rb;
	int h = ceil(a.size() * 0.38);
	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);

	random_device rd;
	mt19937 mt(rd());
	shuffle(AI(b), mt);
	for(int i: b){
		ls = cs;
		cs = Query(i);
		if(cs == ls ^ in) ra.pb(i);
		else rb.pb(i);
	}

	debug(la, lb);
	debug(ra, rb);

	solve(la, ra, !in);
	solve(lb, rb,  in);
}

void Solve(int N) {
	vector<int> hulan;
	for(int i = 1; i <= N * 2; ++i) hulan.pb(i);

	vector<vector<int>> as, bs;
	vector<int> a, b;
	int ls = 0, cs;
	for(int i: hulan){
		cs = Query(i);
		if(cs == ls) b.pb(i);
		else a.pb(i);

		if(a.size() == b.size()){
			as.pb(a);
			bs.pb(b);
			a.clear();
			b.clear();
		}

		ls = cs;
	}
	for(int i = 0; i < as.size(); ++i)
		solve(as[i], bs[i], true);
}

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
      |                 ~~^~~~~~~~~~
minerals.cpp:47:9: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   47 |   if(cs == ls ^ in) ra.pb(i);
      |      ~~~^~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 0; i < as.size(); ++i)
      |                 ~~^~~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:47:9: warning: 'cs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |   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: 5 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10