oj.uz

Submission #781319

# Submission time Handle Problem Language Result Execution time Memory
781319 2023-07-13T03:03:37 Z kebine Detecting Molecules (IOI16_molecules) C++17
0 / 100
 1 ms 300 KB 
// #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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 1, answer = NO)
2 Correct 1 ms 212 KB OK (n = 1, answer = NO)
3 Incorrect 1 ms 300 KB Integer 1 violates the range [0, 0]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Integer 12 violates the range [0, 11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 1, answer = NO)
2 Correct 1 ms 212 KB OK (n = 1, answer = NO)
3 Incorrect 1 ms 300 KB Integer 1 violates the range [0, 0]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 1, answer = NO)
2 Correct 1 ms 212 KB OK (n = 1, answer = NO)
3 Incorrect 1 ms 300 KB Integer 1 violates the range [0, 0]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 1, answer = NO)
2 Correct 1 ms 212 KB OK (n = 1, answer = NO)
3 Incorrect 1 ms 300 KB Integer 1 violates the range [0, 0]
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB OK (n = 1, answer = NO)
2 Correct 1 ms 212 KB OK (n = 1, answer = NO)
3 Incorrect 1 ms 300 KB Integer 1 violates the range [0, 0]
4 Halted 0 ms 0 KB -