Submission #972864

#	Time	Username	Problem	Language	Result	Execution time	Memory
972864		VinhLuu	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	0 ms	348 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[w[i]];
    }
    int ptr = 0;
    vector<int> ans;
    if(w[0] >= L && w[0] <= R){ans.pb(0); return ans;}
    deque<int> dq;
    ll tmp = w[0];
    dq.pb(0);
    for(int i = 0; i < w.size(); i ++){
        dq.push_front(i);
        tmp += w[i];
        if(tmp >= L && tmp <= R){
            while(!dq.empty()){
                ans.pb(a[dq.back()]);
                dq.pop_back();
            }
            sort(all(ans));
            return ans;
        }
        while(!dq.empty() && tmp >= R){
            tmp -= w[dq.back()];
            dq.pop_back();
        }
        if(tmp >= L && tmp <= R){
            while(!dq.empty()){
                ans.pb(a[dq.back()]);
                dq.pop_back();
            }
            sort(all(ans));
            return ans;
        }

    }

    return ans;
}

//#define lpv
#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:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < _w.size(); i ++) w.pb(i);
      |                    ~~^~~~~~~~~~~
molecules.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~
molecules.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i < w.size(); i ++){
      |                    ~~^~~~~~~~~~
molecules.cpp:30:9: warning: unused variable 'ptr' [-Wunused-variable]
   30 |     int ptr = 0;
      |         ^~~

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