Submission #1152367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152367		Esgeer	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	37 ms	8364 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
 
const int mod = 1e9 + 7;
 
using namespace std;
 
const int N = 2e5+5;
const int inf = 1e12;

vector<int32_t> find_subset(int32_t L, int32_t R, vector<int32_t> b) {
    int n = b.size();
    vpi a;
    F(i, 0, n) a.pb({b[i], i});

    sort(a.begin(), a.end());

    vi pref(n, 0);
    vi suff(n, 0);
    pref[0] = a[0].fi;
    F(i, 1, n) pref[i] = pref[i-1] + a[i].fi;
    suff[n-1] = a[n-1].fi;
    for(int i = n-2; i >= 0; i--) suff[i] = suff[i+1] + a[i].fi;

    F(i, 0, n) {
        if(pref[i] >= L && pref[i] <= R) {
            vector<int32_t> res;
            F(j, 0, i+1) res.pb(a[j].se);
            return res;
        }

        if(suff[n-1-i] >= L && suff[n-1-i] <= R) {
            vector<int32_t> res;
            F(j, n-1-i, n) res.pb(a[j].se);
            return res;
        }

        if(pref[i] < L && suff[n-1-i] > R) {
            // ans is somewhere in the middle
            vector<int32_t> res;
            F(j, 0, i+1) res.pb(a[j].se);
            int summy = pref[i];

            F(j, 0, i+1) {
                res[j] = a[n-1-j].se;
                summy -= a[j].fi;
                summy += a[n-1-j].fi;

                if(summy >= L && summy <= R) return res;
            }
        }
    }
    return vector<int32_t>(0);
}

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