| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 225577 | caoash | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma gcc target ("sse4")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "molecules.h";
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define f0xd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define faxd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
template<class t> void ckmin(t &a, t b) { a = min(a, b); }
template<class t> void ckmax(t &a, t b) { a = max(a, b); }
template <class t, int ...ns> struct bit {
t val = 0;
void upd(t v) { val += v; }
t query() { return val; }
};
template <class t, int n, int... ns> struct bit<t, n, ns...> {
bit<t,ns...> bit[n + 1];
template<typename... args> void upd(int pos, args... args) {
for (; pos <= n; pos += (pos&-pos)) bit[pos].upd(args...);
}
template<typename... args> t sum(int r, args... args) {
t res = 0; for (; r; r -= (r&-r)) res += bit[r].query(args...);
return res;
}
template<typename... args> t query(int l, int r, args... args) {
return sum(r,args...)-sum(l-1,args...);
}
};
namespace input {
template<class t> void re(complex<t>& x);
template<class t1, class t2> void re(pair<t1,t2>& p);
template<class t> void re(vector<t>& a);
template<class t, size_t sz> void re(array<t,sz>& a);
template<class t> void re(t& x) { cin >> x; }
void re(double& x) { string t; re(t); x = stod(t); }
void re(ld& x) { string t; re(t); x = stold(t); }
template<class t, class... ts> void re(t& t, ts&... ts) {
re(t); re(ts...);
}
template<class t> void re(complex<t>& x) { t a,b; re(a,b); x = cd(a,b); }
template<class t1, class t2> void re(pair<t1,t2>& p) { re(p.f,p.s); }
template<class t> void re(vector<t>& a) { fax(i,sz(a)) re(a[i]); }
template<class t, size_t sz> void re(array<t,sz>& a) { fax(i,sz) re(a[i]); }
}
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(ll x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(ld x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template<class t1, class t2> void pr(const pair<t1,t2>& x);
template<class t> void pr(const t& x);
template<class t, class... ts> void pr(const t& t, const ts&... ts) {
pr(t); pr(ts...);
}
template<class t1, class t2> void pr(const pair<t1,t2>& x) {
pr("{",x.f,", ",x.s,"}");
}
template<class t> void pr(const t& x) {
pr("{"); // const iterator needed for vector<bool>
bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0;
pr("}");
}
void ps() { pr("\n"); } // print w/ spaces
template<class t, class... ts> void ps(const t& t, const ts&... ts) {
pr(t); if (sizeof...(ts)) pr(" "); ps(ts...);
}
void pc() { pr("]\n"); } // debug w/ commas
template<class t, class... ts> void pc(const t& t, const ts&... ts) {
pr(t); if (sizeof...(ts)) pr(", "); pc(ts...);
}
#define dbg(x...) pr("[",#x,"] = ["), pc(x);
}
using namespace output;
namespace io {
void setin(string s) { freopen(s.c_str(),"r",stdin); }
void setout(string s) { freopen(s.c_str(),"w",stdout); }
void setio(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); // fast i/o
if (sz(s)) { setin(s+".in"), setout(s+".out"); } // for usaco
}
}
using namespace io;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int mod = 1000000007; // 998244353
const ll inf = 1e18;
const int mx = 200005;
const ld pi = 4*atan((ld)1);
vi find_subset(int l, int u, vi w){
vi ret;
set<pi> sufs;
vpi vals;
int n = sz(w);
fax(i,n){
vals.pb(mp(w[i], i));
}
sort(all(vals));
int st = -1; int en = -1;
ll sum = 0;
sufs.insert(mp(0,n));
for(int i = n-1; i >= 0; i--){
sum += vals[i].f;
sufs.insert(mp(sum, i));
}
//dbg(sufs);
sum = 0;
auto fst = sufs.lb(mp(l,int_min));
//dbg(*fst);
if(fst != sufs.end()){
//dbg(u,l,sum+fst->f);
if(sum + fst->f <= u && sum + fst->f >= l){
st = -1; en = fst->s;
}
}
for(int i = 0; i < n; i++){
if(vals[i].f > u){
break;
}
else if(vals[i].f >= l && vals[i].f <= u){
vi ret{vals[i].s};
return ret;
}
sum += vals[i].f;
if(sum > u){
break;
}
auto best = sufs.lb(mp(l-sum, int_min));
//dbg(sum, *best);
if(best != sufs.end()){
if(best->s > i && sum + best->f <= u && sum + best->f >= l){
//dbg(sum + best->f);
st = i;
en = best->s;
}
}
}
//dbg(st,en);
if(st == -1 && en == -1) return ret;
ll tot = 0;
fax(i,st+1) {
ret.pb(vals[i].s);
tot += vals[i].f;
}
f0xd(i,en,n) {
ret.pb(vals[i].s);
tot += vals[i].f;
}
sort(all(ret));
assert(tot >= l && tot <= u);
return ret;
}
/*
int main(){
int n,l,r; re(n,l,r);
vi inp;
fax(i,n){
int x; re(x);
inp.pb(x);
}
vi ret = find_subset(l,r,inp);
fax(i,sz(ret)){
pr(ret[i], " ");
}
}
*/