Submission #146392

#	Time	Username	Problem	Language	Result	Execution time	Memory
146392		dorijanlendvaj	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	524 KiB

messy

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define x first
#define y second
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
const char en='\n';
#include "messy.h"


void flip(string&a,int i)
{
  a[i]='0'+'1'-a[i];
}

bool debug=0;
int rr,ww;

void add(string b)
{
  ++ww;
  add_element(b);
  if (debug) cout<<"added "<<b<<endl;
}

bool check(string b,int r)
{
  ++rr;
  flip(b,r);
  bool x=check_element(b);
  flip(b,r);
  return x;
}

vi restore_permutation(int n, int w, int r) {
  //assert(n==8);
  string b;
  for (int i=0;i<n;++i) b.pb('0');
  for (int i=1;i<n;i*=2)
  {
    string c=b;
    for (int j=0;j<n;++j) if (j&i)
    {
      flip(b,j);
      flip(c,j);
      add(b);
      flip(b,j);
    }
    b=c;
  }
  compile_set();
  string a;
  for (int i=0;i<n;++i) a.pb('0');
  vi ans(n);
  for (int i=0;(1<<i)<n;++i)
  {
    string c=a;
    for (int j=0;j<n;++j) if (check(a,j))
    {
      flip(c,j);
      ans[j]+=1<<i;
    }
    a=c;
  }
  vi bio(n);
  for (auto a: ans) ++bio[a];
  int z=0;
  for (auto a: bio) z+=abs(a-1);
  return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30