Submission #467493

#	Time	Username	Problem	Language	Result	Execution time	Memory
467493		alextodoran	Detecting Molecules (IOI16_molecules)	C++17	Compilation error	0 ms	0 KiB

molecules

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

//#include "molecules.h"

using namespace std;

typedef long long ll;

vector <int> find_subset (int low, int high, vector <int> w)
{
    int n = (int) w.size();

    vector <int> p (n);
    for(int i = 0; i < n; i++)
        p[i] = i;
    sort(p.begin(), p.end(),
         [&] (const int &x, const int &y)
         {
             return w[x] < w[y];
         });

    vector <ll> pref (n);
    for(int i = 0; i < n; i++)
        pref[i] = w[p[i]];
    for(int i = 1; i < n; i++)
        pref[i] += pref[i - 1];

    function <ll (int, int)> seg = [&] (int l, int r)
    {
        return pref[r] - (l == 0 ? 0 : pref[l - 1]);
    };

    for(int len = 1; len <= n; len++)
        if(seg(0, len - 1) <= low && low <= seg(n - len, n - 1))
        {
            int pos = 0;
            while(seg(pos + 1, pos + len) < low)
            {
                pos++;
                assert(pos + len - 1 < n);
            }

            vector <int> answer (len);
            for(int i = 0; i < len; i++)
                answer[i] = pos + i;

            ll sum = seg(pos, pos + len - 1);

            int curr = len - 1;
            while(sum < low)
            {
                assert(curr >= 0);

                sum -= w[p[answer[curr]]];
                answer[curr]++;
                sum += w[p[answer[curr]]];

                curr--;
            }

            assert(low <= sum && sum <= high);

            for(int i = 0; i < len; i++)
                answer[i] = p[answer[i]];

            return answer;
        }
        else if(low <= seg(0, len - 1) && seg(0, len - 1) <= high)
        {
            vector <int> answer (len);
            for(int i = 0; i < len; i++)
                answer[i] = p[i];

            return answer;
        }

    return {};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int low, high;
    cin >> low >> high;

    int n;
    cin >> n;

    vector <int> w (n);
    for(int i = 0; i < n; i++)
        cin >> w[i];

    vector <int> res = find_subset(low, high, w);
    for(int i : res)
        cout << i << " ";
    cout << "\n";

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDd6ds2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXlv1W2.o:molecules.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status