CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-20 16:08:57 +0200
Language:C++
Status:READY
Result:41
Feedback
groupverdictscore
#1ACCEPTED41.3
Test results
testverdicttimescore
#1ACCEPTED0.07 s3.3details
#2ACCEPTED0.26 s4.4details
#3ACCEPTED0.31 s4.3details
#4ACCEPTED0.32 s4.3details
#5ACCEPTED0.32 s4.4details
#6ACCEPTED0.29 s4.3details
#7ACCEPTED0.28 s4.4details
#8ACCEPTED0.30 s4.3details
#9ACCEPTED0.34 s4.3details
#10ACCEPTED0.08 s3.3details

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#define ll long long
#define N (2<<16)

using namespace std;

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#define ll long long
#define N (2<<16)

using namespace std;

int main () {
	int n;
	cin>>n;
	int v[n];
	ll s = 0;
	for (int i = 0; i < n; i++) {
		cin>>v[i];
		s += (long long)v[i];
	}
	while (s / 2 > 2500000) {
		for (int i = 0; i < n; i++) {
			v[i] /= 10;
		}
		s /= 10;
	}
	s /= 2;
	int x[s + 1];
	for (int i = 0; i < s + 1; i++) x[i] = 0;
	x[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int z = s; z >= v[i]; z--) {
			if (x[z]) continue;
			if (x[z - v[i]]) x[z] = i + 1;
		}
	}
	bool b[n];
	//for (int i : x) cout<<i<<" ";
	//cout<<endl;
	for (int i = 0; i < n; i++) b[i] = false;
	for (int i = s; i >= 0; i--) {
		if (x[i]) {
			while (i != 0) {
				//cout<<x[i] - 1<<endl;
				b[x[i] - 1] = true;
				i -= v[x[i] - 1];
			}
			break;
		}
	}
	for (bool r : b) {
		cout<<(2 - (int)r)<<" ";
	}
	cout<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 ...

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 ...

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 ...

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 ...

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 ...

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 ...

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
2 2 1 2 1 1 1 1 1 1 1 1 1 2 1 ...

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 ...

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 ...