Submission #1261845

#TimeUsernameProblemLanguageResultExecution timeMemory
1261845bluevioletDetecting Molecules (IOI16_molecules)C++20
100 / 100
37 ms6728 KiB
#include <bits/stdc++.h> #define ll long long #define io(x) if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);} #define TimeRun {End=clock();cerr<<"Time run: "<<(float)(End-Begin)/CLOCKS_PER_SEC<<"s"<<el;} #define mem(c, x) memset(c, x, sizeof(c)) #define all(c) c.begin(), c.end() #define bit(i,j) ((i >> j) & 1) #define se second #define fi first #define el '\n' using namespace std; template<class X, class Y> bool maximize(X &a, const Y &b) { return (a < b ? a = b, 1 : 0); } template<class X, class Y> bool minimize(X &a, const Y &b) { return (a > b ? a = b, 1 : 0); } int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1}; int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1}; const int maxn = 2e5 + 9; const int Inf = 2e9 + 7; const ll Infll = 1e18 + 9; const ll Mod = 1e9 + 7; /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/ int minn, maxx; ll sum = 0, pref[maxn]; pair<ll,ll> a[maxn]; vector<int> find_subset(int l, int u, vector<int> w) { int n = w.size(); minn = l; maxx = u; ll sum = 0; for (int i=0; i<w.size(); i++) { a[i+1].fi = w[i]; a[i+1].se = i+1; sum += w[i]; } sort(a + 1, a + n + 1); for (int i=1; i<=n; i++) { pref[i] = pref[i-1] + a[i].fi; } vector<int> empt; if (sum < minn || a[1].fi > maxx) return empt; for (int i=1; i<=n; i++) { int l = i, r = n; while (l <= r) { int mid = l + r >> 1; if (pref[mid] - pref[i-1] > maxx) { r = mid - 1; } else if (pref[mid] - pref[i-1] < minn) { l = mid + 1; } else { vector<int> ans; for (int j=i; j<=mid; j++) { ans.push_back(a[j].se - 1); } sort(all(ans)); return ans; } } } return empt; }

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...