oj.uz

Submission #1050538

# Submission time Handle Problem Language Result Execution time Memory
1050538 2024-08-09T10:38:01 Z EntityPlantt Detecting Molecules (IOI16_molecules) C++17
9 / 100
 1 ms 424 KB 
#include "molecules.h"
#include <algorithm>
#include <array>
using namespace std;
vector <int> construct(vector <array <int, 2>> &w, int left, int right) {
	vector <int> ret(left + w.size() - right - 1);
	for (int i = 0; i < left; i++) ret[i] = w[i][1];
	for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1];
	return ret;
}
vector <int> find_subset(int l, int u, vector <int> _w) {
	vector <array <int, 2>> w;
	for (int i = 0; i < _w.size(); i++) w.push_back({_w[i], i});
	long long sum = 0;
	int n = w.size();
	sort(w.begin(), w.end());
	int left = 0, right = n - 1;
	while (right >= 0 && sum < l) sum += w[right--][0];
	if (sum < l) return {};
	if (sum <= u) return construct(w, 0, right);
	while (sum < l || sum > u) {
		sum += w[left++][0];
		if (left == n) return {};
		while (right < n - 1 && sum > u) sum -= w[++right][0];
		if (right == n - 1) return {};
	}
	return construct(w, left, right);
}

Compilation message

molecules.cpp: In function 'std::vector<int> construct(std::vector<std::array<int, 2> >&, int, int)':
molecules.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i = 0; i < w.size() - right - 1; i++) ret[i + left] = w[i + right + 1][1];
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < _w.size(); i++) w.push_back({_w[i], i});
      |                  ~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 10.0

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