Submission #1320003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320003		Thanhs	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	33 ms	5280 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

vector<pair<int, int>> W;

vector<int> sus(vector<int>& v)
{
    vector<int> res;
    for (int t : v)
        res.push_back(W[t].se);
    sort(all(res));
    return res;
}

vector<int> find_subset(int l, int u, vector<int> w) {
    int n = w.size();
    W.resize(n);
    for (int i = 0; i < n; i++)
        W[i] = {w[i], i};
    sort(all(W));
    for (int i = 0; i < n; i++)
        w[i] = W[i].fi;
    vector<long long> p(n, w[0]);
    for (int i = 1; i < n; i++)
        p[i] = p[i - 1] + w[i];
    for (int i = 1; i <= n; i++)
    {
        if (p[i - 1] >= l && p[i - 1] <= u)
        {
            vector<int> res(i);
            iota(all(res), 0);
            return sus(res);
        }
        if (i == n)
            break;
        if (p.back() - p[n - i - 1] >= l && p.back() - p[n - i - 1] <= u)
        {
            vector<int> res(i);
            iota(all(res), n - i);
            return sus(res);
        }
        if (p[i - 1] < l && p.back() - p[n - i - 1] > u)
        {
            vector<int> res(i);
            iota(all(res), 0);
            int cur = p[i - 1], c = n - 1;
            for (int j = i - 1; ; j--)
            {
                if (cur + w[c] - w[j] < l)
                {
                    cur += w[c] - w[j];
                    res[j] = c--;
                    continue;
                }
                while (cur < l)
                    cur += w[res[j] + 1] - w[res[j]], res[j]++;
                return sus(res);
            }
        }
    }
    return vector<int>(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