CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:Metabolix
Submission time:2015-12-20 16:49:06 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#134.1
Test results
testverdicttimescore
#1--0details
#2ACCEPTED1.00 s8.1details
#3--0details
#4ACCEPTED0.99 s8.4details
#5--0details
#6--0details
#7ACCEPTED0.99 s9.1details
#8ACCEPTED0.98 s8.5details
#9--0details
#10--0details

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <time.h>
int main() {
clock_t c0 = clock();
std::mt19937 gen;
int n;
std::cin >> n;
std::vector<int> p(n), a(n), a0;
a.reserve(n);
a0.reserve(n);
long e = 0;
for (int i = 0; i < n; ++i) {
std::cin >> p[i];
a[i] = p[i];
e += p[i];
}
e /= 2;
a0 = a;
long e0 = e;
while (e0 != 0 && (clock() - c0) * 1.0 / CLOCKS_PER_SEC < 0.95) {
for (int i = 0; i < 10000; ++i) {
for (int j = a.size(); j--;) {
std::swap(a[j], a[gen() % a.size()]);
}
for (int& j: a) {
if ((e < 0) == (j < 0)) {
e -= j;
j = -j;
}
if (std::abs(e) < e0) {
e0 = std::abs(e);
a0 = a;
if (e0 == 0) {
goto done;
}
}
}
}
}
done:
for (int i: p) {
auto j = std::find(a0.begin(), a0.end(), i);
if (j != a0.end()) {
a0.erase(j);
std::cout << "1 ";
} else {
std::cout << "2 ";
}
}
std::cout << "\n";
}

Test details

Test 1

Verdict:

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
(empty)

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict:

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
(empty)

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

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

Test 5

Verdict:

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
(empty)

Test 6

Verdict:

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
(empty)

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

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

Test 9

Verdict:

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
(empty)

Test 10

Verdict:

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
(empty)