Submission #927813

#	Time	Username	Problem	Language	Result	Execution time	Memory
927813		huutuan	Broken Device (JOI17_broken_device)	C++14	100 / 100	38 ms	3028 KiB

Anna

#include "Annalib.h"

#include<bits/stdc++.h>

using namespace std;

static int broken[150];
static int ans[150];
static mt19937 rng(69420);

void Anna(int n, long long x, int k, int p[]){
   // int add=rng()%177013;
   // x+=add;
   vector<int> order;
   for (int i=0; i<n; ++i) order.push_back(i);
   shuffle(order.begin(), order.end(), rng);
   memset(broken, 0, sizeof broken);
   memset(ans, 0, sizeof ans);
   for (int i=0; i<k; ++i) broken[p[i]]=1;
   for (int i=0; i<n; i+=2){
      if (broken[order[i]] && broken[order[i+1]]) continue;
      if (broken[order[i]]){
         if (x%3==0){
            ans[order[i]]=0, ans[order[i+1]]=1;
            x/=3;
            continue;
         }
      }
      if (broken[order[i+1]]){
         if (x%3==1){
            ans[order[i]]=1, ans[order[i+1]]=0;
            x/=3;
            continue;
         }
      }
      if (!broken[order[i]] && !broken[order[i+1]]){
         if (x%3==0) ans[order[i]]=0, ans[order[i+1]]=1;
         else if (x%3==1) ans[order[i]]=1, ans[order[i+1]]=0;
         else ans[order[i]]=1, ans[order[i+1]]=1;
         x/=3;
      }
   }
   for (int i=0; i<n; ++i) Set(i, ans[i]);
}

Bruno

#include "Brunolib.h"

#include<bits/stdc++.h>

using namespace std;

static mt19937 rng(69420);

long long Bruno(int n, int a[]){
   // long long add=rng()%177013;
   vector<int> order;
   for (int i=0; i<n; ++i) order.push_back(i);
   shuffle(order.begin(), order.end(), rng);
   long long ans=0;
   long long pw=1;
   for (int i=0; i<n; i+=2){
      if (a[order[i]] || a[order[i+1]]){
         ans+=a[order[i]]*pw*(a[order[i+1]]+1);
         pw*=3;
         if (pw>(long long)1e18) break;
      }
   }
   return ans;
   // return ans-add;
}

• Subtask 1: 100 / 100