CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:Metabolix
Submission time:2015-12-20 13:03:32 +0200
Language:C++
Status:READY
Result:22
Feedback
groupverdictscore
#1ACCEPTED21.5
Test results
testverdicttimescore
#1ACCEPTED1.00 s1.8details
#2ACCEPTED0.97 s10details
#3ACCEPTED0.98 s1.6details
#4ACCEPTED0.99 s0.9details
#5ACCEPTED0.99 s1.4details
#6ACCEPTED0.99 s1.5details
#7ACCEPTED0.98 s0.8details
#8ACCEPTED0.99 s1.1details
#9ACCEPTED1.00 s1details
#10ACCEPTED0.99 s1.4details

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, b;
	long e = 0;
	for (int i = 0; i < n; ++i) {
		std::cin >> p[i];
		a[i] = p[i];
		e += p[i];
	}
	a0 = a;
	long e0 = e;
	while (e0 != 0 && (clock() - c0) * 1.0 / CLOCKS_PER_SEC < 0.95) {
		for (int i = 0; i < 300000; ++i) {
			if (e > 0) {
				std::swap(a[gen() % a.size()], *a.rbegin());
				e -= *a.rbegin() * 2;
				b.push_back(*a.rbegin());
				a.pop_back();
			} else {
				std::swap(b[gen() % b.size()], *b.rbegin());
				e += *b.rbegin() * 2;
				a.push_back(*b.rbegin());
				b.pop_back();
			}
			if (std::abs(e) < std::abs(e0)) {
				e0 = e;
				a0 = a;
				if (e0 == 0) {
					break;
				}
			}
		}
	}
	for (int i: p) {
		auto j = std::find(a.begin(), a.end(), i);
		if (j != a.end()) {
			a.erase(j);
			std::cout << "1 ";
		} else {
			std::cout << "2 ";
		}
	}
	std::cout << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

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

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

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

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

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

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

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

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

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

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

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

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

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

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

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