# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966897 | 2024-04-20T15:09:40 Z | Hugo1729 | Detecting Molecules (IOI16_molecules) | C++11 | 1 ms | 600 KB |
#include <bits/stdc++.h> #include "molecules.h" using namespace std; typedef long long ll; vector<int> find_subset(int l, int u, vector<int> w) { vector<pair<int,int>> sus; for(int i=0;i<w.size();i++)sus.push_back({w[i],i}); sort(w.begin(),w.end()); sort(sus.begin(),sus.end()); int n = w.size(); ll pref[n+1]; pref[0]=0; for(int i=0;i<n;i++)pref[i+1]=pref[i]+w[i]; // for(int i=0;i<n+1;i++)cout << pref[i] << " "; // cout << '\n'; int a=0,b=n; if(pref[n]<u)a=n; else if(pref[1]>u)return vector<int>(0); else{ while(a<b-1){ int mid = (a+b)/2; // cout << a << ' ' << b << ' ' << mid << '\n'; if(pref[mid]<u)a=mid; else b=mid; } } if(a==0||pref[n]<l||pref[a]>u||pref[n]-pref[n-a]<l) return vector<int>(0); int c=0,d=a; while(c<d-1){ int mid=(d+c)/2; // cout << c << ' ' << d << ' ' << mid << ' ' << pref[a-mid]+pref[n]-pref[n-mid] << '\n'; if(pref[a-mid]+pref[n]-pref[n-mid]<u)c=mid; else d = mid; } if(pref[a-c]+pref[n]-pref[n-c]<u)c++; // cout << a << ' ' << c << '\n'; vector<int> ans; for(int i=0;i<a-c;i++)ans.push_back(sus[i].second); for(int i=n-1;i>=n-c;i--)ans.push_back(sus[i].second); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
2 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
3 | Incorrect | 0 ms | 404 KB | Contestant can not find answer, jury can |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | OK (n = 12, answer = YES) |
2 | Correct | 0 ms | 432 KB | OK (n = 12, answer = YES) |
3 | Correct | 0 ms | 600 KB | OK (n = 12, answer = NO) |
4 | Correct | 0 ms | 348 KB | OK (n = 12, answer = NO) |
5 | Incorrect | 0 ms | 348 KB | Contestant can not find answer, jury can |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
2 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
3 | Incorrect | 0 ms | 404 KB | Contestant can not find answer, jury can |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
2 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
3 | Incorrect | 0 ms | 404 KB | Contestant can not find answer, jury can |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
2 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
3 | Incorrect | 0 ms | 404 KB | Contestant can not find answer, jury can |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
2 | Correct | 0 ms | 348 KB | OK (n = 1, answer = NO) |
3 | Incorrect | 0 ms | 404 KB | Contestant can not find answer, jury can |
4 | Halted | 0 ms | 0 KB | - |