CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Omenat
Sender:
Submission time:2015-12-20 17:11:52 +0200
Language:C++
Status:READY
Result:90
Feedback
groupverdictscore
#1ACCEPTED89.9
Test results
testverdicttimescore
#1ACCEPTED0.42 s8.7details
#2ACCEPTED0.20 s9.5details
#3ACCEPTED0.54 s8.6details
#4ACCEPTED0.56 s9.1details
#5ACCEPTED0.29 s8.7details
#6ACCEPTED0.32 s9details
#7ACCEPTED0.28 s8.3details
#8ACCEPTED0.44 s9.5details
#9ACCEPTED0.62 s10details
#10ACCEPTED0.54 s8.5details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:199:10: warning: unused variable 't0' [-Wunused-variable]
  clock_t t0=clock();
          ^
input/code.cpp:206:5: warning: unused variable 'val' [-Wunused-variable]
  ll val=eval(v);
     ^

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
ll p[111];
int n;
const ll inf=1e18;
ll eval(vector<int>&a){
ll v1=0;
ll v2=0;
for (int i=0;i<n;i++){
if (a[i]==1){
v1+=p[i];
}
else{
v2+=p[i];
}
}
return llabs(v1-v2);
}
ll bvb;
int vvv[111];
int bvvv[111];
int rt[1111];
int ri=0;
inline int sl(){
ri++;
if (ri>=1007) ri=0;
return rt[ri];
}
void dfs(vector<pair<ll, int> >&pp, int i, ll p1, ll p2){
if (i==n){
if (llabs(p1-p2)<bvb){
bvb=llabs(p1-p2);
for (int j=0;j<n;j++){
bvvv[j]=vvv[j];
}
}
}
else{
if (p1>p2){
vvv[pp[i].S]=2;
dfs(pp, i+1, p1, p2+pp[i].F);
if (i<10||rand()%11==1){
vvv[pp[i].S]=1;
dfs(pp, i+1, p1+pp[i].F, p2);
}
}
else{
vvv[pp[i].S]=1;
dfs(pp, i+1, p1+pp[i].F, p2);
if (i<10||rand()%11==1){
vvv[pp[i].S]=2;
dfs(pp, i+1, p1, p2+pp[i].F);
}
}
}
}
vector<int> solve3(){
vector<pair<ll, int> > pp(n);
vector<int> r(n);
for (int i=0;i<n;i++){
pp[i]={p[i], i};
}
sort(pp.rbegin(), pp.rend());
bvb=inf;
dfs(pp, 0, 0, 0);
for (int i=0;i<n;i++){
r[i]=bvvv[i];
}
return r;
}
vector<int> solve1(){
vector<pair<ll, int> > pp(n);
vector<int> r(n);
for (int i=0;i<n;i++){
pp[i]={p[i], i};
}
sort(pp.rbegin(), pp.rend());
ll p1=0;
ll p2=0;
for (int i=0;i<n;i++){
if (p1<p2){
p1+=pp[i].F;
r[pp[i].S]=1;
}
else{
p2+=pp[i].F;
r[pp[i].S]=2;
}
}
return r;
}
int ps[111];
int ph[20][55];
int vv[111];
ll ss(int t){
if (ps[t]==0) return 0;
ll bv=inf;
ll bvv=inf;
int bb=0;
for (int i=0;i<(1<<ps[t]);i++){
ll v1=0;
ll v2=0;
for (int j=0;j<ps[t];j++){
if (i&(1<<j)){
v1+=p[ph[t][j]];
}
else{
v2+=p[ph[t][j]];
}
}
if (llabs(v1-v2)<bv){
bv=llabs(v1-v2);
bvv=v1-v2;
bb=i;
}
}
for (int j=0;j<ps[t];j++){
if (bb&(1<<j)){
vv[ph[t][j]]=1;
}
else{
vv[ph[t][j]]=2;
}
}
return bvv;
}
vector<int> solve2(int pk){
int mp=(n-1)/pk+1;
for (int i=0;i<mp;i++){
ps[i]=0;
}
vector<int> asd(n);
for (int i=0;i<n;i++){
asd[i]=i/pk;
}
random_shuffle(asd.begin(), asd.end());
for (int i=0;i<n;i++){
int tp=asd[i];
ph[tp][ps[tp]++]=i;
}
vector<ll> lol;
for (int i=0;i<mp;i++){
lol.push_back(ss(i));
}
int bb=0;
ll bv=inf;
for (int i=0;i<(1<<mp);i++){
ll v=0;
for (int j=0;j<mp;j++){
if (i&(1<<j)){
v-=lol[j];
}
else{
v+=lol[j];
}
}
if (llabs(v)<bv){
bv=llabs(v);
bb=i;
}
}
vector<int> r(n);
for (int j=0;j<mp;j++){
if (bb&(1<<j)){
for (int t=0;t<ps[j];t++){
vv[ph[j][t]]=3-vv[ph[j][t]];
}
}
}
for (int i=0;i<n;i++){
r[i]=vv[i];
}
return r;
}
int main(){
srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i=0;i<1007;i++){
rt[i]=rand()%11;
}
cin>>n;
//n=100;
clock_t t0=clock();
vector<pair<ll, int> > pp(n);
for (int i=0;i<n;i++){
cin>>p[i];
//p[i]=rand();
}
vector<int> v=solve3();
ll val=eval(v);
/*
while (1){
vector<int> tv=solve2(10);
if (eval(tv)<val){
v=tv;
}
clock_t t1=clock();
if (((double)(t1-t0)/CLOCKS_PER_SEC)>0.9) break;
}
*/
for (int i=0;i<n;i++){
cout<<v[i]<<" ";
}
}

Test details

Test 1

Verdict: ACCEPTED

input
95
779724552 231968220 985023789 ...

correct output
(empty)

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

Test 2

Verdict: ACCEPTED

input
85
229722261 51722691 862338862 8...

correct output
(empty)

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

Test 3

Verdict: ACCEPTED

input
97
398995377 989444445 634573915 ...

correct output
(empty)

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

Test 4

Verdict: ACCEPTED

input
99
843687873 164010938 51269970 4...

correct output
(empty)

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

Test 5

Verdict: ACCEPTED

input
90
864611617 418460939 773297829 ...

correct output
(empty)

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

Test 6

Verdict: ACCEPTED

input
92
289890246 25801423 763027596 7...

correct output
(empty)

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

Test 7

Verdict: ACCEPTED

input
89
879039800 50522278 850785072 4...

correct output
(empty)

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

Test 8

Verdict: ACCEPTED

input
96
27192469 222283781 681532515 1...

correct output
(empty)

user output
2 2 1 2 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
2 2 1 1 2 1 1 2 1 1 1 2 2 1 1 ...

Test 10

Verdict: ACCEPTED

input
98
612168861 979831717 671087051 ...

correct output
(empty)

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