Submission #972838

#	Time	Username	Problem	Language	Result	Execution time	Memory
972838		VinhLuu	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	1 ms	604 KiB

molecules

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
int block = 555;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

int n, a[N];

vector<int> find_subset(int L,int R,vector<int> _w){
    vector<int> w;
    for(int i = 0; i < _w.size(); i ++) w.pb(i);
    sort(all(w), [&] (int x,int y){return _w[x] < _w[y];});
    for(int i = 0; i < w.size(); i ++){
        a[i] = w[i];
        w[i] = _w[i];
    }
    int ptr = 0;
    vector<int> ans;
    if(w[0] >= L && w[0] <= R){ans.pb(0); return ans;}
    int tmp = w[0];
    for(int i = 1; i < w.size(); i ++){
        while(ptr < i - 1 && tmp + w[i] < L) tmp += w[++ptr];
        while(ptr >= 0 && tmp + w[i] - w[ptr] >= L) tmp -= w[ptr--];
        if(tmp + w[i] >= L && tmp + w[i] <= R){
            for(int j = 0; j <= ptr; j ++) ans.pb(a[j]);
            ans.pb(a[i]);
            sort(all(ans));
            return ans;
        }
        if(tmp + w[i] < L) continue;
        int l = 0, r = ptr, mid, pos = -1, X = tmp - R;
        while(l <= r){
            mid = (l + r) / 2;
            if(w[mid] >= X){
                pos = mid;
                r = mid - 1;
            }else l = mid + 1;
        }
        if(pos != -1 && tmp + w[i] - w[pos] >= L && tmp + w[i] - w[pos] <= R){
            for(int j = 0; j <= ptr; j ++) if(j != pos) ans.pb(a[j]);
            ans.pb(a[i]);
            sort(all(ans));
            return ans;
        }
    }
    return ans;
}


#ifdef lpv

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

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    int l, u; cin >> l >> u;
    int x;
    vector<int> input;
    while (cin >> x) input.push_back(x);

    for (auto i : find_subset(l, u, input))
    cout << i << ' ';
}
#endif // lpv

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < _w.size(); i ++) w.pb(i);
      |                    ~~^~~~~~~~~~~
molecules.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~
molecules.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 1; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~

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