CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:Henrik Lievonen
Submission time:2015-12-20 17:00:18 +0200
Language:C++
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED32.5
Test results
testverdicttimescore
#1ACCEPTED0.42 s2.9details
#2ACCEPTED0.40 s3.1details
#3ACCEPTED0.44 s2.9details
#4ACCEPTED0.44 s3.1details
#5ACCEPTED0.41 s3.6details
#6ACCEPTED0.41 s3details
#7ACCEPTED0.40 s3.3details
#8ACCEPTED0.44 s4.3details
#9ACCEPTED0.44 s3.3details
#10ACCEPTED0.41 s3details

Code

// G

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long int ull;

mt19937 mt(0);
uniform_int_distribution<> flip(1, 2);
vector<pair<ull, int>> apples;

void print(const vector<char> &r) {
  for (char c : r)
    cout << c << '\n';
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ull a;
    cin >> a;
    apples.push_back(make_pair(a, i));
  }
  
  vector<char> naive(n);
  ull naived;
  {
    ull u = 0;
    ull m = 0;
    for (int i = 0; i < n; i++) {
      auto a = apples[i];
      if (u > m) {
	naive[i] = '2';
	m += a.first;
      } else {
	naive[i] = '1';
	u += a.first;
      }
    }
    naived = min(u-m, m-u);
  }
  vector<char> sorted(n);
  ull sortedd = 1ull<<60;
  {
    sort(apples.begin(), apples.end());
    ull u = 0;
    ull m = 0;
    for (int i = n-1; i >= 0; i--) {
      auto a = apples[i];
      if (u > m) {
	sorted[a.second] = '2';
	m += a.first;
      } else {
	sorted[a.second] = '1';
	u += a.first;
      }
    }
    sortedd = min(u-m, m-u);
  }
  
  vector<char> bitthing(n);
  ull bitthingd = 1ull<<60;
  {
    const int bits = min(n, 20);
    for (int k = 0; k < (1<<bits); k++) {
      ull u = 0;
      ull m = 0;
      int i = n-1;
      for (int j = 0; j < bits; j++, i--) {
	auto a = apples[i];
	if (k & (1<<j)) {
	  sorted[a.second] = '2';
	  m += a.first;
	} else {
	  sorted[a.second] = '1';
	  u += a.first;
	} 
      }
      for (; i >= 0; i--) {
	auto a = apples[i];
	if (u > m) {
	  sorted[a.second] = '2';
	  m += a.first;
	} else {
	  sorted[a.second] = '1';
	  u += a.first;
	}
      }
      sortedd = min(u-m, m-u);
    }
  }
  
  if (naived < sortedd && naived < bitthingd) {
    print(naive);
  } else if (sortedd < naived && sortedd < bitthingd) {
    print(sorted);
  } else if (bitthingd < naived && bitthingd < sortedd) {
    print(bitthing);
  } else {
    print(sorted);
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
1
2
2
1
1
...

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
1
1
2
1
2
...

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
1
2
1
2
2
...

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
2
2
1
1
2
...

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
2
1
1
2
2
...

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
1
2
1
1
1
...

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
2
1
2
1
1
...

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
2
2
1
2
2
...

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
2
2
2
1
1
...

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
1
2
1
1
1
...