oj.uz

Submission #754548

# Submission time Handle Problem Language Result Execution time Memory
754548 2023-06-08T03:32:54 Z Olympia Bootfall (IZhO17_bootfall) C++17
13 / 100
 1000 ms 340 KB 
#include <vector>
#include <iostream>
#include <cassert>
#include <random>
#include <cmath>
#include <map>
#include <algorithm>
#include <bitset>
#include <set>
#include <stack>
using namespace std;
vector<int> cnt; //cnt[i] is number of ways to achieve sum of i
int sum = 0;
void print () {
	for (int x: cnt) {
		cout << x << ' ';
	}
	cout << endl;
}
void add (int x) {
	//cout << "ADD " << x << endl;
	sum += x;
	for (int i = (int)cnt.size() - 1; i >= x; i--) {
		cnt[i] += cnt[i - x];
	}
}
void rem (int x) {
	//cout << "REM " << x << endl;
	sum -= x;
	for (int i = 0; i <= (int)cnt.size() - x - 1; i++) {
		cnt[i + x] -= cnt[i];
	}
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cnt.assign(5000, 0);
    cnt[0] = 1;
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
    	cin >> v[i];
    	add(v[i]);
    }
    vector<int> ans;
    for (int i = 1; i < 5000; i++) {
    	bool fine = true;
    	if (sum % 2 != 0 or !cnt[sum/2]) {
    		fine = false;
    	}
    	add(i);
    	for (int j = 0; j < v.size(); j++) {
    		rem(v[j]);
    		if (sum % 2 == 1 or !cnt[sum/2]) {
    			fine = false;
    		}
    		add(v[j]);
    	}
    	rem(i);
    	if (fine) {
    		ans.push_back(i);
    	}
    }
    cout << ans.size() << endl;
    for (int i: ans) {
    	cout << i << ' ';
    }
    cout << endl;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |      for (int j = 0; j < v.size(); j++) {
      |                      ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct
10 Correct 719 ms 320 KB Output is correct
11 Correct 934 ms 320 KB Output is correct
12 Correct 751 ms 320 KB Output is correct
13 Correct 721 ms 332 KB Output is correct
14 Correct 729 ms 324 KB Output is correct
15 Correct 900 ms 320 KB Output is correct
16 Correct 977 ms 332 KB Output is correct
17 Correct 507 ms 340 KB Output is correct
18 Correct 646 ms 340 KB Output is correct
19 Correct 704 ms 320 KB Output is correct
20 Correct 728 ms 212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct
10 Correct 719 ms 320 KB Output is correct
11 Correct 934 ms 320 KB Output is correct
12 Correct 751 ms 320 KB Output is correct
13 Correct 721 ms 332 KB Output is correct
14 Correct 729 ms 324 KB Output is correct
15 Correct 900 ms 320 KB Output is correct
16 Correct 977 ms 332 KB Output is correct
17 Correct 507 ms 340 KB Output is correct
18 Correct 646 ms 340 KB Output is correct
19 Correct 704 ms 320 KB Output is correct
20 Correct 728 ms 212 KB Output is correct
21 Execution timed out 1069 ms 340 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct
10 Correct 719 ms 320 KB Output is correct
11 Correct 934 ms 320 KB Output is correct
12 Correct 751 ms 320 KB Output is correct
13 Correct 721 ms 332 KB Output is correct
14 Correct 729 ms 324 KB Output is correct
15 Correct 900 ms 320 KB Output is correct
16 Correct 977 ms 332 KB Output is correct
17 Correct 507 ms 340 KB Output is correct
18 Correct 646 ms 340 KB Output is correct
19 Correct 704 ms 320 KB Output is correct
20 Correct 728 ms 212 KB Output is correct
21 Execution timed out 1069 ms 340 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct
10 Correct 719 ms 320 KB Output is correct
11 Correct 934 ms 320 KB Output is correct
12 Correct 751 ms 320 KB Output is correct
13 Correct 721 ms 332 KB Output is correct
14 Correct 729 ms 324 KB Output is correct
15 Correct 900 ms 320 KB Output is correct
16 Correct 977 ms 332 KB Output is correct
17 Correct 507 ms 340 KB Output is correct
18 Correct 646 ms 340 KB Output is correct
19 Correct 704 ms 320 KB Output is correct
20 Correct 728 ms 212 KB Output is correct
21 Execution timed out 1069 ms 340 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212 KB Output is correct
2 Correct 162 ms 320 KB Output is correct
3 Correct 138 ms 320 KB Output is correct
4 Correct 106 ms 320 KB Output is correct
5 Correct 298 ms 320 KB Output is correct
6 Correct 203 ms 316 KB Output is correct
7 Correct 158 ms 320 KB Output is correct
8 Correct 292 ms 340 KB Output is correct
9 Correct 251 ms 320 KB Output is correct
10 Correct 719 ms 320 KB Output is correct
11 Correct 934 ms 320 KB Output is correct
12 Correct 751 ms 320 KB Output is correct
13 Correct 721 ms 332 KB Output is correct
14 Correct 729 ms 324 KB Output is correct
15 Correct 900 ms 320 KB Output is correct
16 Correct 977 ms 332 KB Output is correct
17 Correct 507 ms 340 KB Output is correct
18 Correct 646 ms 340 KB Output is correct
19 Correct 704 ms 320 KB Output is correct
20 Correct 728 ms 212 KB Output is correct
21 Execution timed out 1069 ms 340 KB Time limit exceeded
22 Halted 0 ms 0 KB -