Submission #1140704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140704		Math4Life2020	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	42 ms	6364 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
using ui = __int128;

vector<ll> SOLVE(vector<ll> v0) {
  ui cval = 0;
  ui fib[103];
  fib[0]=0;
  fib[1]=1;
  fib[2]=1;
  for (ll i=3;i<103;i++) {
    fib[i]=fib[i-1]+fib[i-2];
  }
  for (ll i=0;i<100;i++) {
    if (v0[i]==1) {
      cval += fib[i+2];
    }
  }
  vector<ll> v1(70,0);
  for (ll i=0;i<70;i++) {
    v1[i]=(ll)(((ui)cval>>i)%(ui)2);
  }
  return v1;
}

vector<ll> ENCRYPT(vector<ll> v0) {
  vector<ll> vf;
  for (ll T=0;T<1000;T++) {
    vector<ll> v1;
    for (ll i=0;i<100;i++){
      v1.push_back(v0[i+100*T]);
    }
    v1 = SOLVE(v1);
    for (ll x: v1) {
      vf.push_back(x);
    }
  }
  return vf;
}

void Anna(int N, vector<char> S) {
    bool xfnd = 0;
    vector<ll> vsend;
    for (ll i=0;i<N;i++) {
        if (S[i]=='X' && !xfnd) {
            xfnd = 1;
            vsend.push_back(1);
            vsend.push_back(0);
        } else if (xfnd && S[i]=='Z' && (i==(N-1)||(S[i+1]!='Z'))) {
            vsend.push_back(1);
        } else {
            vsend.push_back(0);
        }
    }
    while (vsend.size()<100000) {
      vsend.push_back(0);
    }
    while (vsend.size()>100000) {
      vsend.pop_back();
    }
    vsend = ENCRYPT(vsend);
    for (ll x: vsend) {
      Send(x);
    }
}

Bruno

#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
using ui = __int128;
#include "Bruno.h"

vector<ll> wipe1(vector<ll> v0, ll N) {
  vector<ll> v1;
  bool f1 = 0;
  for (ll i=0;i<(v0.size());i++) {
    v1.push_back(v0[i]);
    if (v0[i]==1 && f1==0) {
      f1 = 1;
      i++;
    }
  }
  while (v1.size()<N) {
    v1.push_back(1);
  }
  return v1;
}

vector<ll> SOLVE(vector<ll> v0) {
  vector<ll> v1(100,0);
  ui cnum = 0;
  for (ll i=0;i<70;i++) {
    cnum += v0[i]*(((ui)1)<<i);
  }
  ui fib[103];
  fib[0]=0;
  fib[1]=1;
  fib[2]=1;
  for (ll i=3;i<103;i++) {
    fib[i]=fib[i-1]+fib[i-2];
  }
  while (cnum>0) {
    for (ll T=101;T>=2;T--) {
      if (cnum>=fib[T]) {
        v1[T-2]=1;
        cnum -= fib[T];
      }
    }
  }
  return v1;
}

vector<ll> DCRYPT(vector<ll> v0) {
  vector<ll> vf;
  for (ll T=0;T<1000;T++) {
    vector<ll> v1;
    for (ll i=0;i<70;i++) {
      v1.push_back(v0[70*T+i]);
    }
    v1 = SOLVE(v1);
    for (ll x: v1) {
      vf.push_back(x);
    }
  }
  return vf;
}

void Bruno(int N, int L, vector<int> A) {
    ll cx = -1;
    stack<ll> s0;
    A = DCRYPT(A);
    A = wipe1(A,100000);
    for (ll i=0;i<N;i++) {
        if (A[i]==1) {
            if (cx==-1) {
                cx = i;
            } else {
                while (!s0.empty()) {
                    Remove((int)s0.top()); s0.pop();
                }
                Remove(i);
            }
        } else {
            if (cx==-1) {
                Remove(i);
            } else {
                s0.push(i);
            }
        }
    }
    while (!s0.empty()) {
        Remove((int)s0.top()); s0.pop();
    }
    if (cx != -1) {
        Remove(cx);
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95