Submission #736348

#	Time	Username	Problem	Language	Result	Execution time	Memory
736348		snowman	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	50 ms	8680 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}



const int mxa = 1e9 + 1;
// string __fname = "exclusiv";  
// ifstream in(__fname + ".in"); 
// ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out


vector<int> find_subset(int L, int U, vector<int> w){
    int n = w.size();
    vector<pll> a(n);
    fri(0, n){
        a[i] = {w[i], i};
    }
    sort(all(a));
    vector<ll> pre(n);
    fri(0, n){
        pre[i] = a[i].st;
        if(i) pre[i] += pre[i - 1];
    }
    ll l = 1, r = n ,rsl = -1, rsr = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        ll s;
        if(n - 1 - mid == -1){
            s = pre[n - 1];
        }
        else s = pre[n - 1] - pre[n - 1 - mid];
        if(s < L){
            l = mid + 1;
            continue;
        }
        else{
            ll i = 1;
            while(s > U && n - i - mid >= -1){
                if(n - i - mid == -1){
                    s = pre[n - i];
                }
                else s = pre[n - i] - pre[n - i - mid];
                i++;
            }
            if(i != 1) i--;
            if(s <= U && s >= L){
                rsr = n - i;
                rsl = n - i - mid + 1;
                break;
            }
            else{
                r = mid - 1;
                continue;
            }
        }
    }
    vector<int> rs;
    if(rsl == -1 || rsr == -1){
        return rs;
    }
    fri(rsl, rsr + 1){
        rs.pb(a[i].nd);
    }
    return rs;
}

// int main(){
//     vector<int> rs;
//     vector<int> w = {10};
//     rs = find_subset(1, 10 ,w);
//     for(auto i : rs){
//         cout << i << '\n';
//     }
// }

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