Submission #586922

#	Time	Username	Problem	Language	Result	Execution time	Memory
586922		tranxuanbach	Detecting Molecules (IOI16_molecules)	C++17	100 / 100	43 ms	7116 KiB

molecules

#ifndef FEXT

#include "molecules.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

const int N = 2e5 + 5;

vi find_subset(int losum, int hisum, vi a){
    int n = isz(a);

    vpii b(n);
    For(i, 0, n){
        b[i] = make_pair(a[i], i);
    }
    sort(bend(b));
    vector <ll> pb(n, 0);
    For(i, 0, n){
        pb[i] = (i ? pb[i - 1] : 0) + b[i].fi;
    }

    ForE(len, 1, n){
        ll sumlo = pb[len - 1], sumhi = pb[n - 1] - (n - len ? pb[n - len - 1] : 0);
        if (hisum < sumlo or sumhi < losum){
            continue;
        }
        ll sum = sumlo;
        int idxl = len - 1, idxr = n;
        while (hisum < sum or sum < losum){
            sum -= b[idxl].fi;
            idxl--;
            idxr--;
            sum += b[idxr].fi;
        }
        vi vans;
        ForE(i, 0, idxl){
            vans.emplace_back(b[i].se);
        }
        For(i, idxr, n){
            vans.emplace_back(b[i].se);
        }
        return vans;
    }
    return {};
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int n, l, u;
    assert(3 == scanf("%d %d %d", &n, &l, &u));
    std::vector<int> w(n);
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &w[i]));
    std::vector<int> result = find_subset(l, u, w);
    
    
    printf("%d\n", (int)result.size());
    for (int i = 0; i < (int)result.size(); i++)
        printf("%d%c", result[i], " \n"[i == (int)result.size() - 1]);
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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