Submission #1149181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149181		duckindog	Broken Device (JOI17_broken_device)	C++17	100 / 100	40 ms	1424 KiB

Anna

#include <bits/stdc++.h>

using namespace std;

#include "Annalib.h"

void Anna( int N, long long X, int K, int P[] ){
  vector<int> per(N); iota(per.begin(), per.end(), 0);
  shuffle(per.begin(), per.end(), mt19937_64(149973));

  vector<bool> work(N, true);  
  for (int i = 0; i < K; ++i) 
    work[P[i]] = false;

  vector<int> num;
  { // decompose x into base 3
    while (X) { 
      num.push_back(X % 3);
      X /= 3;
    }
  }

  auto chk = [&](int pos0, int pos1, int value) { 
    int p0 = work[pos0], p1 = work[pos1];
    int statePos = (p0 << 1) | (p1 << 0);
    int stateVal = value + 1;
    return (statePos & stateVal) == stateVal;
  };

  for (int i = 0; i < N; i += 2) {
    int pos0 = per[i], pos1 = per[i + 1];
    
    if (!num.size() || !chk(pos0, pos1, num.back())) {
      Set(pos0, 0);
      Set(pos1, 0);
      continue;
    }
    int statePos = num.back() + 1; num.pop_back();
    
    Set(pos0, statePos >> 1 & 1);
    Set(pos1, statePos & 1);
  }
}

Bruno

#include <bits/stdc++.h>

using namespace std;

#include "Brunolib.h"

long long Bruno( int N, int A[] ){
  vector<int> per(N); iota(per.begin(), per.end(), 0);
  shuffle(per.begin(), per.end(), mt19937_64(149973));

  long long X = 0;
  for (int i = 0; i < N; i += 2) { 
    int p0 = A[per[i]], p1 = A[per[i + 1]];
    if (!p0 && !p1) continue;
    
    int value = ((p0 << 1) | (p1 << 0)) - 1;
    X = X * 3 + value;
  }
  return X;
}

• Subtask 1: 100 / 100