Submission #1152140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152140		Esgeer	Detecting Molecules (IOI16_molecules)	C++20	69 / 100	70 ms	12724 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
//# define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
 
const int mod = 1e9 + 7;
 
using namespace std;
 
const int N = 2e5+5;
const int inf = 1e12;

vector<int> find_subset(int L, int R, vector<int> b) {
    int n = b.size();
    vpi a;
    F(i, 0, n) a.pb({b[i], i});
    
    sort(a.begin(), a.end());
    int smaller = -1;
    int curSum = 0;
    F(i, 0, n) {
        curSum += a[i].fi;
        if(curSum >= L) {
            if(curSum <= R) {
                vi res;
                F(j, 0, i+1) res.pb(a[j].se);
                return res;
            }
            break;
        }
        smaller = i;
    }

    if(smaller != -1) {
        set<pii> elements;
        int summy = 0;
        F(i, 0, smaller+1) {
            elements.insert(a[i]);
            summy += a[i].fi;
        }

        priority_queue<pii> pq;
        F(i, smaller+1, n) {
            pq.push(a[i]);
        }

        while(pq.size()) {
            pii nw = pq.top();
            pii old = *elements.begin();
            if(old.fi >= nw.fi) {
                break; // no need for more;
            }

            elements.erase(elements.begin());
            elements.insert(nw);;
            pq.pop();
            summy -= old.fi;
            summy += nw.fi;

            if(summy >= L) {
                vi res;
                for(pii el : elements) res.pb(el.se);
                return res;
            }

            if(summy > R) break; // exceeded the threshold, somehow :/
        }
    }
    return vi(0);
}

Compilation message (stderr)

molecules.cpp:23:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   23 | const int inf = 1e12;
      |                 ^~~~
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: 0 / 31