Submission #229879

#TimeUsernameProblemLanguageResultExecution timeMemory
229879xyzyzlDetecting Molecules (IOI16_molecules)C++14
69 / 100
55 ms4984 KiB
// Time: // Algorithms: #include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; #define MAXN 1000005 #define FOR(i, n) for (int i = 0; i < n; i++) #define FORR(j, i, n) for (int i = j; i < n; i++) #define FORD(i, n) for (int i = n - 1; i >= 0; i--) #define F1R(i, n) for (int i = 1; i <= n; i++) #define F1RD(i, n) for (int i = n; i >= 1; i--) #define pb push_back #define mp make_pair #define endl '\n' #define DUEHOANG \ ios_base::sync_with_stdio(0); \ cin.tie(NULL); \ cout.tie(NULL) #define fileio(in, out) \ freopen(in, "r", stdin); \ freopen(out, "w", stdout); #define ll long long #define MOD (1e9*1)+7 #define MOD2 998244353 #define INF (1e9*1)+5 typedef set<int> si; typedef vector<int> vi; typedef pair<int, int> pii; typedef pair<int, pii> iii; typedef vector<pii> vii; typedef vector<iii> viii; typedef priority_queue<int> pqi; typedef stack<int> sti; typedef queue<int> qi; typedef deque<int> di; typedef map<int, int> mii; #define f first #define s second #define LEFT(x) 2 * x #define RIGHT(x) 2 * x + 1 #define bitinc(x) x&-x const int MAX(int &a, int b) { return a = max(a, b); } const int MIN(int &a, int b) { return a = min(a, b); } vi find_subset(int l, int u, vi w) { int n = w.size(); vii nw(n); for(int i = 0; i < w.size(); i++) { nw[i] = mp(w[i], i); } sort(nw.begin(), nw.end()); // you need indices so you kinda can't do this! // sort(w.begin(), w.end()); int i = 0, j = 0, rsm = 0; vi ans; while(i < n) { while(i < n && rsm < l) { rsm += nw[i].f; i++; } while(j < i && rsm > u) { rsm -= nw[j].f; j++; } if(l <= rsm && rsm <= u) { // this is good for(int k = j; k < i; k++) ans.pb(nw[k].s); break; } } // are you supposed to put the subset in inc order too or smth // whatever sort(ans.begin(), ans.end()); return ans; }

Compilation message (stderr)

molecules.cpp: In function 'vi find_subset(int, int, vi)':
molecules.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < w.size(); i++)
                 ~~^~~~~~~~~~
#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...