Submission #142576

#TimeUsernameProblemLanguageResultExecution timeMemory
142576andreiomdDetecting Molecules (IOI16_molecules)C++11
100 / 100
480 ms37708 KiB
#include <bits/stdc++.h> #include "molecules.h" using namespace std; const int NMAX = 2e5 + 5; int N, A[NMAX], B[NMAX]; long long dp[NMAX]; map < int, vector < int > > mp; map < int, int > H; static long long Sum (int Left, int Right) { if(Left > Right) return 0LL; return dp[Right] - dp[Left - 1]; } vector < int > find_subset (int l, int u, vector < int > w) { int N = (int)w.size(); for(int i = 0; i < N; ++i) { A[i + 1] = w[i]; mp[A[i + 1]].push_back(i); H[A[i + 1]] = 0; } sort(A + 1, A + N + 1); for(int i = 1; i <= N; ++i) dp[i] = dp[i - 1] + 1LL * A[i]; bool Ok = false; int Left = 1, Right = 0; for(Left = 1, Right = 0; Left <= N && Right <= N; ++Left) { while(Sum(Left, Right) < l && Left <= N && Right <= N) ++Right; if(Sum(Left, Right) >= l && Sum(Left, Right) <= u) { Ok = true; break; } while(Sum(Left, Right) > u && Left <= N && Right <= N) ++Left; if(Sum(Left, Right) >= l && Sum(Left, Right) <= u) { Ok = true; break; } } vector < int > Sol; if(Ok) { for(int i = Left; i <= Right; ++i) { Sol.push_back(mp[A[i]][H[A[i]]]); ++H[A[i]]; } } return Sol; }
#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...