Submission #417617

#TimeUsernameProblemLanguageResultExecution timeMemory
417617TricksterDetecting Molecules (IOI16_molecules)C++14
0 / 100
1 ms204 KiB
//Suleyman Atayew #include "molecules.h" #include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <bitset> #include <queue> #include <cmath> #include <map> #include <set> #define N 200010 #define ff first #define ss second #define pb push_back #define ll long long #define mod 1000000007 #define pii pair <int, int> #define sz(a) (int)(a.size()) ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; } using namespace std; int n; int v[N]; int p[N][5]; pii arr[N]; vector <int> find_subset(int l, int u, vector <int> w) { n = sz(w); for(int i = 1; i <= n; i++) arr[i] = {w[i-1], i-1}; sort(arr + 1, arr+n+1); sort(w.begin(), w.end()); for(int i = 1; i <= n; i++) v[i] = w[i-1], p[i][0] = p[i-1][0] + v[i]; for(int i = n; i >= 1; i--) p[i][1] = p[i+1][1] + v[i]; for(int i = 1; i <= n; i++) { vector <int> ret; if(p[i][0] >= l && p[i][0] <= u) { for(int h = 1; h <= i; h++) ret.pb(arr[h].ss); return ret; } if(p[i][1] >= l && p[n-i+1][1] <= u) { for(int h = 1; h <= i; h++) ret.pb(arr[n-h+1].ss); return ret; } if(p[i][0] <= l && p[n-i+1][1] >= u) { int sum = 0; for(int h = i, j = n; h >= 1; h--, j--) { if(sum + v[j] <= u) { sum += v[j]; ret.pb(arr[j].ss); } else if(sum + v[h] <= u) { sum += v[h]; ret.pb(arr[h].ss); } } if(sum >= l && sum <= u) { return ret; } } } vector <int> ret; return ret; }
#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...