Submission #781319

#	Time	Username	Problem	Language	Result	Execution time	Memory
781319		kebine	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1 ms	300 KiB

molecules

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

// # define int long long
# define fir first
# define sec second
# define pb push_back

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

int n, l2, u2;
vector<int> wei;
int presuml[cnst];
int presumr[cnst];

void presums() {
    for(int i = 0; i<n; i++) presuml[i+1] = presuml[i]+wei[i];
    for(int i = n-1; i>=0; i--) presumr[i+1] = presumr[i+2]+wei[i]; 
}

vector<int> check(int x) {
    vector<int> idx;
    int lo = presuml[x];
    int hi = presumr[n-x+1];

    // cerr << x << " " << lo << " " << hi << endl;
    if(hi < l2 || lo > u2) return idx;


    for(int i = 0; i<=x; i++) {
        int y = presuml[i];
        int z = presumr[n-(x-i)+1];
        if(l2 <= y+z && y+z <= u2) {
            for(int j = 1; j<=i; j++) idx.pb(j);
            for(int j = n-(x-i)+1; j<=n; j++) idx.pb(j);
            return idx;
        }
    }
    return idx;
}

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    wei = w, l2 = l, u2 = u;
    n = wei.size();

    presums();

    int lo = 1;
    int hi = n;
    int res = 0;
    vector<int> ans;

    while(lo <= hi) {
        int mid = (lo+hi)/2;

        vector<int> x = check(mid);
        // cerr << mid << " ";
        // for(auto v: x) cerr << v << " "; cerr << endl;

        if(!x.empty()) lo = mid+1, res = mid, ans = x;
        else hi = mid-1;
    }

    // cerr << res << endl;

    return ans;
}

/*

signed main() {
    ios_base::sync_with_stdio(false);
    // int t = 1;
    // if(mutipletestcase) cin >> t; 
    // while(t--) solve();

    int n, l, u; cin >> n >> l >> u;
    vector<int> vec(n);
    for(int i = 0; i<n; i++) cin >> vec[i];
    vector<int> ans = find_subset(l, u, vec);

    for(auto v: ans) cout << v << " ";
}
*/

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:53:9: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   53 |     int res = 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