Submission #342126

#	Time	Username	Problem	Language	Result	Execution time	Memory
342126		Karliver	Detecting Molecules (IOI16_molecules)	C++14	100 / 100	78 ms	7168 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(12)<<(x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i, b) for (int i=0; i<b; ++i)
using ll = long long;
const int mod = (ll)998244353;
#define PI acos(-1)
typedef pair<int , int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 2e6 + 2;
const double eps = 1e-7;

vector<int> find_subset(int l, int r, vector<int> a) {



    int n = a.size();
    vector<pairs>b(n);
    for(int i = 0;i < n; ++i) {

        b[i] = {a[i], i};
    }

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

    vector<ll>pre(n + 1, 0);
    pre[0] = 0;
    for(int i = 0;i < n; ++i) {
        pre[i + 1] = pre[i] + a[i];
    }

    auto cmp = [&](int pos) {
        int ls = a[pos] + r - l;
        int low = pos;
        int high = upper_bound(a.begin() + pos, a.end(), ls) - a.begin();
        --high;


        int ans = -1;
        while(low < high) {
            int mid = (low + high) / 2;
            ll ps = pre[mid + 1] - pre[pos];

            if(ps >= l && ps <= r ) {
                ans = mid;
                break;
            }
            if(ps < l) {
                low = mid + 1;
            }
            else high = mid;
        }
        ll ss = pre[low + 1] - pre[pos];
        if(ss >= l && ss <= r) ans = low;
        return ans;
    };

    int st = -1;
    int ed = -1;

    for(int i = 0;i < n; ++i) {
        int ans = cmp(i);
        if(ans == -1)continue;
        st = i;
        ed = ans;
        break;
    }
    if(st == -1)return vector<int>(0);
    int sz = ed - st + 1;

    vector<int>ans;
    for(int i = st;i <= ed;++i)ans.push_back(b[i].second);

    return ans;


}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:74:9: warning: unused variable 'sz' [-Wunused-variable]
   74 |     int sz = ed - st + 1;
      |         ^~

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