Submission #489341

#	Time	Username	Problem	Language	Result	Execution time	Memory
489341		joshjms	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	41 ms	6204 KiB

molecules

#include "molecules.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define konaqua ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define otsuaqua exit(0);
 
#define debug(x) cout << #x << " => " << x << "\n"
#define all(x) x.begin(), x.end()
#define sp " "

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
const ll INFF = 1e18 + 5;
const ll INF = 1e10 + 5;
const int MX = 1e6 + 5;
const int MXL = 105;
const int mod = 1e9 + 7; // (use when CF)
// const int mod = 998244353; // (use when Atcoder)
const double ERROR = 1e-7;

const ld pi = 3.14159265358979323846;

const int set_inf = 0x3f3f3f3f;

int N, L, R, S;
pair <int,int> A[2000005];
vector <int> emp, ans;
queue <pair<int,int>> Q;

vector<int> find_subset(int l, int u, vector<int> w) {
    N = w.size();
    L = R = 0;

    for(int i = 0; i < N; i++){
        A[i].fi = w[i];
        A[i].se = i;
    }

    sort(A, A + N);

    for(; R < N; R++){
        S += A[R].fi;
        Q.push(A[R]);

        while(S > u){
            S -= Q.front().fi;
            Q.pop();
            L++;
        }

        if(l <= S && S <= u){
            break;
        }
    }

    if(S < l || S > u) return emp;

    for(; Q.size(); Q.pop())
        ans.push_back(Q.front().se);

    sort(all(ans));
    return ans;
}

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