oj.uz

Submission #77090

# Submission time Handle Problem Language Result Execution time Memory
77090 2018-09-21T03:46:36 Z shoemakerjo Detecting Molecules (IOI16_molecules) C++14
0 / 100
 1000 ms 556 KB 
#include "molecules.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;

map<ll, set<int>> indos;

vector<int> find_subset(int l, int u, vector<int> w) {
    sort(w.begin(), w.end());
    multiset<ll> curin;
    multiset<ll> curout;
    ll csum = 0;

    for (int i = 0; i < w.size(); i++) {
    	if (indos.count(w[i])) {
    		indos[w[i]].insert(i);
    	}
    	else {
    		set<int> stuff;
    		stuff.insert(i);
    		indos[w[i]] = stuff;

    	}
    	curout.insert(w[i]);
    }

    while (csum < l) {
    	if (curout.size() == 0) break;
    	if (csum + *curout.begin() <= u) {
    		csum += *curout.begin();
    		curin.insert(*curout.begin());
    		curout.erase(curout.begin());
    	}
    	else {
    		ll val = *curout.rbegin();
    		ll oval = *curin.begin();
    		if (val < oval) break;
    		csum += val-oval;
    		curout.erase(--curout.end());
    		curin.erase(curin.begin());
    		curin.insert(val);
    		curout.insert(oval);
    	}
    }
    if (csum < l) {
    	vector<int> ans;
    	return ans;
    }
    vector<int> ans;
    for (ll vv : curin) {
    	ans.push_back(*indos[vv].begin());
    	indos[vv].erase(indos[vv].begin());
    }
    return ans;
}

Compilation message

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < w.size(); i++) {
                     ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB OK (n = 1, answer = NO)
2 Execution timed out 1075 ms 380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB OK (n = 12, answer = YES)
2 Correct 2 ms 476 KB OK (n = 12, answer = YES)
3 Correct 2 ms 556 KB OK (n = 12, answer = NO)
4 Execution timed out 1089 ms 556 KB Time limit exceeded
5 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 Execution timed out 1075 ms 380 KB Time limit exceeded
3 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 Execution timed out 1075 ms 380 KB Time limit exceeded
3 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 Execution timed out 1075 ms 380 KB Time limit exceeded
3 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 Execution timed out 1075 ms 380 KB Time limit exceeded
3 Halted 0 ms 0 KB -