Submission #1301164

#TimeUsernameProblemLanguageResultExecution timeMemory
1301164Math4Life2020Detecting Molecules (IOI16_molecules)C++20
100 / 100
37 ms8332 KiB
#include "molecules.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; vector<int> find_subset(int _l, int _u, vector<int> _w) { ll N = _w.size(); ll l = _l; ll u = _u; //sort(w.begin(),w.end()); vector<pii> pw; for (ll x=0;x<N;x++) { pw.push_back({_w[x],x}); } sort(pw.begin(),pw.end()); ll w[N]; for (ll i=0;i<N;i++) { w[i]=pw[i].first; } vector<int> vf; ll pfs[N+1]; pfs[0]=0; for (ll t=0;t<N;t++) { pfs[t+1]=pfs[t]+w[t]; } for (ll T=1;T<=N;T++) { ll smin = pfs[T]; ll smax = pfs[N]-pfs[N-T]; //cout << "T="<<T<<", smin="<<smin<<", smax="<<smax<<"\n"; if (smax<l || u<smin) { continue; } //cout << "f1\n"; for (ll xl=0;xl<T;xl++) { ll bs0 = pfs[xl]+pfs[N]-pfs[N-T+xl+1]; //0, 1, 2, ..., xl-1 //and //N-(T-xl-1), N-(T-xl-2), ..., N-2, N-1 ll vmin = bs0 + w[xl]; ll vmax = bs0 + w[N-T+xl]; //cout << "xl="<<xl<<", vmin="<<vmin<<", vmax="<<vmax<<"\n"; if (vmax<l || u<vmin) { continue; } //cout << "f2\n"; vector<int> vans; for (ll t=0;t<xl;t++) { vans.push_back(pw[t].second); } for (ll t=(N-T+xl+1);t<N;t++) { vans.push_back(pw[t].second); } for (ll t=xl;t<=(N-T+xl);t++) { if (l<=(bs0+w[t])&&(bs0+w[t])<=u) { vans.push_back(pw[t].second); return vans; } } } } return vf; }

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...