CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2016-01-05 15:43:31 +0200
Language:C++
Status:READY
Result:88
Feedback
groupverdictscore
#1ACCEPTED88.1
Test results
testverdicttimescore
#1ACCEPTED0.84 s7.9details
#2ACCEPTED0.80 s10details
#3ACCEPTED0.90 s9.5details
#4ACCEPTED0.93 s10details
#5ACCEPTED0.83 s8.2details
#6ACCEPTED0.86 s9.1details
#7ACCEPTED0.82 s8.5details
#8ACCEPTED0.88 s7.4details
#9ACCEPTED0.89 s8.6details
#10ACCEPTED0.83 s8.9details

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;


vector<pair<int, int> > p;

bool srt(pair<int, int> a, pair<int, int> b){ return a.first>b.first;}


int jako[101];
int tulos[101];
long long paras;


int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  paras=100000000000000ll;
  
  cin >> n;
  p.resize(n);
  for (int i=0; i!=n; ++i){
    cin >> p[i].first;
    p[i].second=i;
  }sort(p.begin(), p.end(), srt);
  
  int b=min(n-1, 22);
  int bt=1<<b;
  ++b;
  
  long long sa;
  long long sb;
  int i, j;
  long long d;
  for (i=0; i!=bt; ++i){
    sa=0; sb=0;
    for (j=0; j!=b; ++j){
      if (i&(1<<j)){
        sa+=p[j].first;
        jako[j]=1;
      }else{
        sb+=p[j].first;
        jako[j]=2;
      }
    }
    for (j=b; j!=n; ++j){
      if (sa<sb){
        sa+=p[j].first;
        jako[j]=1;
      }else{
        sb+=p[j].first;
        jako[j]=2;
      }
    }
    d=sa-sb;
    if (d<0) d=-d;
    if (d<paras){
      for (j=0; j!=n; ++j) tulos[p[j].second]=jako[j];
      paras=d;
    }
  }
  for (i=0; i!=n; ++i) cout << tulos[i] << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

user output
2
2
2
2
1
...

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

user output
1
1
2
2
1
...

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

user output
1
1
1
1
1
...

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

user output
2
2
1
2
1
...

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

user output
1
1
2
2
1
...

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

user output
2
1
2
2
2
...

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

user output
1
2
2
1
1
...

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
1
1
1
1
1
...

Test 9

Verdict: ACCEPTED

input
100
186459081 254674429 394007236 ...

correct output
(empty)

user output
1
1
2
2
1
...

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

user output
1
2
2
1
1
...