Submission #637639

#	Time	Username	Problem	Language	Result	Execution time	Memory
637639		ggoh	Unscrambling a Messy Bug (IOI16_messy)	C++14	49 / 100	2 ms	340 KiB

messy

#include "messy.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
bool C;
int ch[128],p;
vector<int> restore_permutation(int n, int w, int r) {
    vector<int>ans;
    vector<int>rev;
    for(int i=0;i<n;i++)
    {
      ans.push_back(i);
      rev.push_back(i);
    }
    string a[129],b;
    for(int i=0;i<n;i++)
    {
      a[0]+='0';
      a[n]+='1';
    }
    a[0][0]='1';
    add_element(a[0]);
    a[0][0]='0';
    for(int i=2;i<n;i+=2)
    {
        for(int j=0;j<i;j++)a[i]+='1';
        for(int j=i;j<n;j++)a[i]+='0';
        add_element(a[i]);
        swap(a[i][i-1],a[i][i]);
        add_element(a[i]);
        a[n][i-1]='0';
        add_element(a[n]);
        a[n][i-1]='1';
    }
    compile_set();
    p=0;
    for(int i=0;i<n-1;i++)
    {
      b=a[0];
      b[i]='1';
      if(check_element(b))
      {
        p=1;
        rev[0]=i;
        break;
      }
    }
    if(!p)rev[0]=n-1;
    for(int i=2;i<n;i+=2)
    {
      b=a[0];
      for(int j=0;j<i-1;j++)
      {
        b[rev[j]]='1';
      }
      vector<int>h;
      for(int j=0;j<n;j++)
      {
        if(b[j]!='1')
        {
          b[j]='1';
          if(check_element(b))
          {
            h.push_back(j);
          }
          b[j]='0';
        }
      }
      a[n][h[0]]='0';
      if(check_element(a[n]))
      {
        rev[i-1]=h[0];
        rev[i]=h[1];
      }
      else
      {
        rev[i]=h[0];
        rev[i-1]=h[1];
      }
      a[n][h[0]]='1';
    }

    for(int i=0;i<n-1;i++)ch[rev[i]]=1;
    for(int i=0;i<n;i++)if(ch[i]==0)rev[n-1]=i;
    for(int i=0;i<n;i++)ans[rev[i]]=i;

    return ans;
}

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