답안 #754548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754548	2023-06-08T03:32:54 Z	Olympia	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1000 ms	340 KB

bootfall

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #754548

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0