Submission #1305141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305141		thelegendary08	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	39 ms	10008 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
#define int long long 
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
std::vector<signed> find_subset(signed l, signed u, std::vector<signed> w) {
	vector<signed>ans = {}; int n = w.size(); vpii g; f0r(i,n)g.eb(w[i],i); sort(g.begin(),g.end());
	vi v(n); f0r(i, n)v[i] = g[i].first; int L = l, R = u; 
	vi pref(n+1); pref[0] = 0; FOR(i,1,n+1)pref[i] = pref[i-1] + v[i-1]; 
	vi suf(n+1); suf[0] = 0; for(int i = n-1; i >= 0; i--)suf[n-i] = suf[n-i-1] + v[i]; 
	for(int s = 1; s <= n; s++){
		if(pref[s] > R || suf[s] < L)continue; 
		int lo = 0, hi = s; while(lo < hi){
			int mid = lo + (hi - lo) / 2;
			int sum = pref[s - mid] + suf[mid]; if(sum >= L && sum <= R){
				f0r(i,s-mid)ans.pb(g[i].second); for(int i = n-1; i >= n-mid; i--)ans.pb(g[i].second); break;
			}
			if(sum < L)lo = mid + 1; 
			else hi = mid - 1; 
		}
		if(!ans.empty())break;
		int mid = lo; 
		int sum = pref[s - mid] + suf[mid]; if(sum >= L && sum <= R){
			f0r(i,s-mid)ans.pb(g[i].second); for(int i = n-1; i >= n-mid; i--)ans.pb(g[i].second); break;
		}
		if(!ans.empty())break;
	}
	return ans; 
}

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
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31