oj.uz

Submission #196932

# Submission time Handle Problem Language Result Execution time Memory
196932 2020-01-17T18:19:38 Z Swan Detecting Molecules (IOI16_molecules) C++14
9 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>
#include "molecules.h"
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("cowrect.in","r",stdin)
#define OUTP freopen ("cowrect.out","w",stdout)
using namespace std;



vector<int> find_subset(int l, int u, vector<int> w) {
    vector<pair<int,int> > start;
    for(int i(0); i < w.size();i++){
        start.push_back({w[i],i});
    }
    sort(start.begin(),start.end());
    sort(w.begin(),w.end());
    if(w[0] > u)return {};
    long long res = 0;
    for(int i(0); i < w.size();i++){
        res+=w[i];
    }
    if(res < l)return {};
    if(res>=l && res<=u){
        vector<int> ans;
        for(int i(0); i < start.size();i++)ans.push_back(start[i].second);
        return ans;
    }
    res = 0;
    set<pair<int,int> > s;
    int cnt = 0;
    int pnt = 0;
    for(int i(0); i < w.size();i++){
        if(res + w[i] > u)break;
        res+=w[i];
        cnt++;
        s.insert({w[i],i});
        pnt++;
    }
    //cout << res << ' ' << cnt << endl;
    vector<int> v;
    //return {w.size()};
    while(cnt){
        int now = s.begin()->first;
        res-=now;
        res+=w[pnt];
        s.erase(s.begin());
        s.insert({w[pnt],pnt});
        pnt++;
        cnt--;
        //cout << res << ' ' << l << ' ' << u << endl;
        if(res>=l && res <=u){
            int pnt = 0;
            for(auto& a: s)v.push_back(start[a.second].second);
            return v;
        }
        if(pnt == w.size())break;
    }
    //cout << res << endl;
    return {};
}

/*
main(){
    ios_base::sync_with_stdio(0);
    int l,u,n; cin >> l >> u >> n;
    vector<int> v;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        v.push_back(x);
    }
    vector<int> ans = find_subset(l,u,v);
    for(int i(0); i < ans.size();i++)cout << ans[i] << ' ';
    return 0;
}
*/
/*
15 17 4
6 8 8 7
14 15 4
5 5 6 6
10 20 4
15 17 16 18
0 0 5
10 10 10 10 10
*/

Compilation message

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < w.size();i++){
                   ~~^~~~~~~~~~
molecules.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < w.size();i++){
                   ~~^~~~~~~~~~
molecules.cpp:26:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i(0); i < start.size();i++)ans.push_back(start[i].second);
                       ~~^~~~~~~~~~~~~~
molecules.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < w.size();i++){
                   ~~^~~~~~~~~~
molecules.cpp:53:17: warning: unused variable 'pnt' [-Wunused-variable]
             int pnt = 0;
                 ^~~
molecules.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pnt == w.size())break;
            ~~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Correct 2 ms 376 KB OK (n = 1, answer = NO)
3 Correct 2 ms 256 KB OK (n = 1, answer = YES)
4 Correct 2 ms 376 KB OK (n = 2, answer = YES)
5 Correct 2 ms 376 KB OK (n = 2, answer = YES)
6 Correct 1 ms 504 KB OK (n = 3, answer = YES)
7 Correct 2 ms 256 KB OK (n = 3, answer = YES)
8 Correct 2 ms 380 KB OK (n = 3, answer = YES)
9 Correct 2 ms 256 KB OK (n = 3, answer = YES)
10 Correct 2 ms 256 KB OK (n = 3, answer = YES)
11 Correct 2 ms 376 KB OK (n = 3, answer = YES)
12 Correct 2 ms 376 KB OK (n = 3, answer = YES)
13 Correct 2 ms 256 KB OK (n = 3, answer = NO)
14 Correct 2 ms 256 KB OK (n = 3, answer = YES)
15 Correct 2 ms 376 KB OK (n = 3, answer = YES)
16 Correct 2 ms 376 KB OK (n = 3, answer = NO)
17 Correct 2 ms 376 KB OK (n = 3, answer = NO)
18 Correct 2 ms 380 KB OK (n = 100, answer = NO)
19 Correct 2 ms 376 KB OK (n = 100, answer = YES)

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB OK (n = 12, answer = YES)
2 Correct 2 ms 376 KB OK (n = 12, answer = YES)
3 Correct 2 ms 376 KB OK (n = 12, answer = NO)
4 Correct 2 ms 376 KB OK (n = 12, answer = NO)
5 Incorrect 2 ms 376 KB Contestant can not find answer, jury can
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Correct 2 ms 376 KB OK (n = 1, answer = NO)
3 Correct 2 ms 256 KB OK (n = 1, answer = YES)
4 Correct 2 ms 376 KB OK (n = 2, answer = YES)
5 Correct 2 ms 376 KB OK (n = 2, answer = YES)
6 Correct 1 ms 504 KB OK (n = 3, answer = YES)
7 Correct 2 ms 256 KB OK (n = 3, answer = YES)
8 Correct 2 ms 380 KB OK (n = 3, answer = YES)
9 Correct 2 ms 256 KB OK (n = 3, answer = YES)
10 Correct 2 ms 256 KB OK (n = 3, answer = YES)
11 Correct 2 ms 376 KB OK (n = 3, answer = YES)
12 Correct 2 ms 376 KB OK (n = 3, answer = YES)
13 Correct 2 ms 256 KB OK (n = 3, answer = NO)
14 Correct 2 ms 256 KB OK (n = 3, answer = YES)
15 Correct 2 ms 376 KB OK (n = 3, answer = YES)
16 Correct 2 ms 376 KB OK (n = 3, answer = NO)
17 Correct 2 ms 376 KB OK (n = 3, answer = NO)
18 Correct 2 ms 380 KB OK (n = 100, answer = NO)
19 Correct 2 ms 376 KB OK (n = 100, answer = YES)
20 Correct 2 ms 348 KB OK (n = 12, answer = YES)
21 Correct 2 ms 376 KB OK (n = 12, answer = YES)
22 Correct 2 ms 376 KB OK (n = 12, answer = NO)
23 Correct 2 ms 376 KB OK (n = 12, answer = NO)
24 Incorrect 2 ms 376 KB Contestant can not find answer, jury can
25 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Correct 2 ms 376 KB OK (n = 1, answer = NO)
3 Correct 2 ms 256 KB OK (n = 1, answer = YES)
4 Correct 2 ms 376 KB OK (n = 2, answer = YES)
5 Correct 2 ms 376 KB OK (n = 2, answer = YES)
6 Correct 1 ms 504 KB OK (n = 3, answer = YES)
7 Correct 2 ms 256 KB OK (n = 3, answer = YES)
8 Correct 2 ms 380 KB OK (n = 3, answer = YES)
9 Correct 2 ms 256 KB OK (n = 3, answer = YES)
10 Correct 2 ms 256 KB OK (n = 3, answer = YES)
11 Correct 2 ms 376 KB OK (n = 3, answer = YES)
12 Correct 2 ms 376 KB OK (n = 3, answer = YES)
13 Correct 2 ms 256 KB OK (n = 3, answer = NO)
14 Correct 2 ms 256 KB OK (n = 3, answer = YES)
15 Correct 2 ms 376 KB OK (n = 3, answer = YES)
16 Correct 2 ms 376 KB OK (n = 3, answer = NO)
17 Correct 2 ms 376 KB OK (n = 3, answer = NO)
18 Correct 2 ms 380 KB OK (n = 100, answer = NO)
19 Correct 2 ms 376 KB OK (n = 100, answer = YES)
20 Correct 2 ms 348 KB OK (n = 12, answer = YES)
21 Correct 2 ms 376 KB OK (n = 12, answer = YES)
22 Correct 2 ms 376 KB OK (n = 12, answer = NO)
23 Correct 2 ms 376 KB OK (n = 12, answer = NO)
24 Incorrect 2 ms 376 KB Contestant can not find answer, jury can
25 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Correct 2 ms 376 KB OK (n = 1, answer = NO)
3 Correct 2 ms 256 KB OK (n = 1, answer = YES)
4 Correct 2 ms 376 KB OK (n = 2, answer = YES)
5 Correct 2 ms 376 KB OK (n = 2, answer = YES)
6 Correct 1 ms 504 KB OK (n = 3, answer = YES)
7 Correct 2 ms 256 KB OK (n = 3, answer = YES)
8 Correct 2 ms 380 KB OK (n = 3, answer = YES)
9 Correct 2 ms 256 KB OK (n = 3, answer = YES)
10 Correct 2 ms 256 KB OK (n = 3, answer = YES)
11 Correct 2 ms 376 KB OK (n = 3, answer = YES)
12 Correct 2 ms 376 KB OK (n = 3, answer = YES)
13 Correct 2 ms 256 KB OK (n = 3, answer = NO)
14 Correct 2 ms 256 KB OK (n = 3, answer = YES)
15 Correct 2 ms 376 KB OK (n = 3, answer = YES)
16 Correct 2 ms 376 KB OK (n = 3, answer = NO)
17 Correct 2 ms 376 KB OK (n = 3, answer = NO)
18 Correct 2 ms 380 KB OK (n = 100, answer = NO)
19 Correct 2 ms 376 KB OK (n = 100, answer = YES)
20 Correct 2 ms 348 KB OK (n = 12, answer = YES)
21 Correct 2 ms 376 KB OK (n = 12, answer = YES)
22 Correct 2 ms 376 KB OK (n = 12, answer = NO)
23 Correct 2 ms 376 KB OK (n = 12, answer = NO)
24 Incorrect 2 ms 376 KB Contestant can not find answer, jury can
25 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Correct 2 ms 376 KB OK (n = 1, answer = NO)
3 Correct 2 ms 256 KB OK (n = 1, answer = YES)
4 Correct 2 ms 376 KB OK (n = 2, answer = YES)
5 Correct 2 ms 376 KB OK (n = 2, answer = YES)
6 Correct 1 ms 504 KB OK (n = 3, answer = YES)
7 Correct 2 ms 256 KB OK (n = 3, answer = YES)
8 Correct 2 ms 380 KB OK (n = 3, answer = YES)
9 Correct 2 ms 256 KB OK (n = 3, answer = YES)
10 Correct 2 ms 256 KB OK (n = 3, answer = YES)
11 Correct 2 ms 376 KB OK (n = 3, answer = YES)
12 Correct 2 ms 376 KB OK (n = 3, answer = YES)
13 Correct 2 ms 256 KB OK (n = 3, answer = NO)
14 Correct 2 ms 256 KB OK (n = 3, answer = YES)
15 Correct 2 ms 376 KB OK (n = 3, answer = YES)
16 Correct 2 ms 376 KB OK (n = 3, answer = NO)
17 Correct 2 ms 376 KB OK (n = 3, answer = NO)
18 Correct 2 ms 380 KB OK (n = 100, answer = NO)
19 Correct 2 ms 376 KB OK (n = 100, answer = YES)
20 Correct 2 ms 348 KB OK (n = 12, answer = YES)
21 Correct 2 ms 376 KB OK (n = 12, answer = YES)
22 Correct 2 ms 376 KB OK (n = 12, answer = NO)
23 Correct 2 ms 376 KB OK (n = 12, answer = NO)
24 Incorrect 2 ms 376 KB Contestant can not find answer, jury can
25 Halted 0 ms 0 KB -