Submission #1078526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078526		anton	Broken Device (JOI17_broken_device)	C++17	85 / 100	47 ms	3024 KiB

Anna

#include "Annalib.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long 

int N;
ll X;


void Anna( int _N, long long _X, int K, int P[] ){
  ll XOR = 22334263684363467LL;
  srand(42);

  N = _N;
  X = _X;

  vector<int> base3;
  X = X^XOR;
  while(X>0){
    base3.push_back(X%3LL);
    X/=3LL;
  }

  


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

  vector<int> res(N);
  auto mySet = [&](int pos, int val){
    if(pos<N){
      res[pos] = val;
    }
  };

  vector<int> info_bits;
  for(auto e: base3){
    if(e==0){
      info_bits.push_back(0);
      info_bits.push_back(1);
    }
    else if(e==1){
      info_bits.push_back(1);
      info_bits.push_back(0);
    }
    else if(e==2){
      info_bits.push_back(1);
      info_bits.push_back(1);
    }
  }
  /*for(auto e: info_bits){
    //cout<<e<<" ";
  }
  //cout<<endl;*/

  int cur_pos = 0;
  int cur_bit =(rand()%base3.size())*2;
  //cout<<"blocks "<<base3.size()<<endl;
  vector<bool> written(base3.size(), false);
  int nb_rem = base3.size();
  while(cur_pos<N && nb_rem>0){
    if((!info_bits[cur_bit]) || (!broken[cur_pos])){
      if((!info_bits[cur_bit+1]) || (!broken[cur_pos+1])){
        if(broken[cur_pos]|| broken[cur_pos+1]){
        }
        //cout<<cur_pos<<", "<<cur_bit<<" | ";
        res[cur_pos] =info_bits[cur_bit];
        res[cur_pos+1] = info_bits[cur_bit+1];
        written[cur_bit/2] = true;
        nb_rem--;
      }
    }
    if(nb_rem == 0){
      break;
    }
    cur_bit = (rand()%base3.size())*2;
    while(written[cur_bit/2]){
      cur_bit = (rand()%base3.size())*2;
    }
    
    cur_pos+=2;
  }
  //cout<<endl;
  for(int i = 0; i<N; i++){
    Set(i, res[i]);
  }
}

Bruno

#include "Brunolib.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long 

long long Bruno( int N, int A[] ){
  ll XOR = 22334263684363467LL;
  srand(42);


  
  ll res= 0;

  /*for(auto e: bits){
    //cout<<e<<" ";
  }
  //cout<<endl;*/
  int nb_blocks = 0;
  for(int i = 0; i<N; i+=2){
    if(A[i] == 0 && A[i+1] == 0){
    }
    else{
      nb_blocks++;
    }
  }
  vector<int> bits(2*nb_blocks);

  int block_id = (rand()%nb_blocks)*2;
  //cout<<"blocks "<<nb_blocks<<endl;

  int nb_rem = nb_blocks;
  for(int i = 0; i<N && nb_rem>0; i+=2){
    if(A[i] == 0 && A[i+1] == 0){
      
    }
    else{
      //cout<<i<<", "<<block_id<<" | ";
      bits[block_id] = A[i];
      bits[block_id+1] = A[i+1];
      nb_rem--;
    }
    if(nb_rem == 0){
      break;
    }
    block_id = (rand()%nb_blocks)*2;
    while((bits[block_id]!= 0) || (bits[block_id+1]!=0)){
      block_id = (rand()%nb_blocks)*2;
    }
  }
  //cout<<endl;
  vector<int> base3(nb_blocks);

  for(int i = 0; i<nb_blocks*2; i+=2){
    if(bits[i] == 0 && bits[i+1] == 1){
      base3[i/2] = 0;
    }
    if(bits[i] == 1 && bits[i+1] == 0){
      base3[i/2] = 1;

    }
    if(bits[i] == 1 && bits[i+1] == 1){
      base3[i/2] = 2;
    }
  }

  ll X= 0;

  while(base3.size()>0){
    X*=3LL;
    X += (ll)(base3.back());
    base3.pop_back();
  }
  X = X^XOR;

  //cout<<X<<endl;
  return X;

}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:34:8: warning: variable 'mySet' set but not used [-Wunused-but-set-variable]
   34 |   auto mySet = [&](int pos, int val){
      |        ^~~~~

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:13:6: warning: unused variable 'res' [-Wunused-variable]
   13 |   ll res= 0;
      |      ^~~

• Subtask 1: 85 / 100