Submission #1062447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062447		sleepntsheep	Flights (JOI22_flights)	C++17	0 / 100	3 ms	6476 KiB

Ali

#include "Ali.h"
#include <string>
#include <array>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

constexpr int BASE=1e9,D=99;
struct bigint{
  array<ll,D>v{};
  bigint(ll x){ v[0]=x;}
  bigint() {}
  int cmpr(const bigint &o)const { for(int i=D-1;i>=0;--i)if(v[i]!=o.v[i])return v[i]<o.v[i]?-1:1; return 0; };
  const bigint& operator+=(const bigint&o){
    ll carry=0;
    for(int i=0;i<D;++i){
      v[i]=(carry+o.v[i]+v[i]);
      carry=v[i]/BASE;
      v[i]%=BASE;
    }
    return *this;
  }
  const bigint& operator-=(const bigint&o){
    for(int i=0;i<D;++i){
      v[i]=(v[i]-o.v[i]);
      if(v[i]<0)v[i]+=BASE,v[i+1]--;
    }
    return*this;
  }
  const bigint& operator*=(ll x){
    ll carry=0;
    for(int i=0;i<D;++i){
      v[i]=(v[i]*x+carry);
      carry=v[i]/BASE;
      v[i]%=BASE;
    }
    return *this;
  }
  friend bigint operator+(bigint&lhs,bigint&rhs){return lhs+=rhs;}
  friend bigint operator-(bigint&lhs,bigint&rhs){return lhs-=rhs;}
  friend bigint operator*(bigint&lhs,ll rhs){return lhs*=rhs;}
  bool operator<(const bigint &o)const{return cmpr(o)==-1;}
  bool operator>(const bigint &o)const{return cmpr(o)==1;}
  bool operator>=(const bigint &o)const{return cmpr(o)>=0;}
  bool operator<=(const bigint &o)const{return cmpr(o)<=0;}
  bool operator==(const bigint &o)const{return cmpr(o)==0;}
};


namespace {
  const int N=30000;
  std::vector<int> g[N];
  int hld[N],par[N],sz[N],dep[N];
  void dfs(int u,int p){ dep[u]=dep[par[u]=p]+1;int best=0; sz[u]=1;for(auto &v:g[u])if(v-p){ dfs(v,u),sz[u]+=sz[v]; if(sz[v]>best)swap(v,g[u][0]),best=sz[v]; } }
  void efs(int u){ for(auto v:g[u])if(v-par[u]) hld[v]=(v==g[u][0])?hld[u]:v,efs(v); }
  int lca(int u,int v){ while(hld[u]-hld[v]){ if(dep[hld[u]]<dep[hld[v]])swap(u,v); u=par[hld[u]]; } return dep[u]<dep[v]?u:v; }
  int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
  ll read(string&s,int i,int b=14){ int z=0; for(int j=0;j<b;++j)z|=((s[i+j]-'0'))<<j; return z; }

  int nn;
  ll valid_enc(ll enc){ return enc/10000<nn and enc%10000<nn; }
  ll XX(ll enc){return enc/10000;}
  ll YY(ll enc){return enc%10000;}

  const int B2=1210;
  bigint pw2[3000];
  bigint npow[4000];int inited;
  string to_string(bigint &b){ string T; for(int i=B2-1;i>=0;--i) if(b<pw2[i]) T+='0'; else T+='1',b-=pw2[i]; return T; }
  void init(){ if(inited)return; inited=1; npow[0]=1; for(int i=1;i<4000;++i) npow[i]=npow[i-1]*10000;
    pw2[0]=1;for(int i=1;i<B2;++i)pw2[i]=pw2[i-1]*2; }
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
  init();
  ::nn = N;
  for(int i=0;i<N;++i)g[i].clear(),hld[i]=0,par[i]=0,sz[i]=0,dep[i]=0;
  for(int i=0;i+1<N;++i)g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
  for(int i=0;i<N;++i)SetID(i,i);
  dfs(0,0);
  hld[0]=0;efs(0);
}

std::string SendA(std::string S) {
  init();

  ll enc=read(S,0,20);
  vector<int>dis;
  for(ll j=0;j<(1<<7);++j){
    ll enc2 = (enc&((1<<20)-1)) | (j<<20);
    if(valid_enc(enc2))dis.push_back(dist(XX(enc2),YY(enc2)));
  }

  bigint b;
  for(int i=0;i<(int)dis.size();++i)b+=npow[i]*dis[i];
  return to_string(b);
}

Benjamin

#include "Benjamin.h"
#include <array>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

constexpr int BASE=1e9,D=99;
struct bigint{
  array<ll,D>v{};
  bigint(ll x){ v[0]=x;}
  bigint() {}
  int cmpr(const bigint &o)const {
    for(int i=D-1;i>=0;--i)if(v[i]!=o.v[i])return v[i]<o.v[i]?-1:1;
    return 0;
  };
  const bigint& operator+=(const bigint&o){
    ll carry=0;
    for(int i=0;i<D;++i){
      v[i]=(carry+o.v[i]+v[i]);
      carry=v[i]/BASE;
      v[i]%=BASE;
    }
    return *this;
  }
  const bigint& operator-=(const bigint&o){
    for(int i=0;i<D;++i){
      v[i]=(v[i]-o.v[i]);
      if(v[i]<0)v[i]+=BASE,v[i+1]--;
    }
    return*this;
  }
  const bigint& operator*=(ll x){
    ll carry=0;
    for(int i=0;i<D;++i){
      v[i]=(v[i]*x+carry);
      carry=v[i]/BASE;
      v[i]%=BASE;
    }
    return *this;
  }
  friend bigint operator+(bigint&lhs,bigint&rhs){return lhs+=rhs;}
  friend bigint operator-(bigint&lhs,bigint&rhs){return lhs-=rhs;}
  friend bigint operator*(bigint&lhs,ll rhs){return lhs*=rhs;}
  bool operator<(const bigint &o)const{return cmpr(o)==-1;}
  bool operator>(const bigint &o)const{return cmpr(o)==1;}
  bool operator>=(const bigint &o)const{return cmpr(o)>=0;}
  bool operator<=(const bigint &o)const{return cmpr(o)<=0;}
  bool operator==(const bigint &o)const{return cmpr(o)==0;}
};


namespace {
  int yy,nn;
  ll enc_;
  ll valid_enc(ll enc){ return enc/10000<nn and enc%10000<nn; }

  const int B2=1346;
  bigint pw2[3000];
  bigint npow[4000];int inited;
  bigint from_string(string &T){ bigint b; for(int i=0;i<(int)T.size();++i)if(T[i]=='1')b+=pw2[i]; return b; }
  void init(){ if(inited)return; inited=1; npow[0]=1; for(int i=1;i<4000;++i) npow[i]=npow[i-1]*10000;
    pw2[0]=1;for(int i=1;i<B2;++i)pw2[i]=pw2[i-1]*2; }
}

std::string SendB(int N, int X, int Y) {
  init();
  ::nn=N;
  string S(20,'0');
  ll enc=10000ll*X+Y;
  for(ll j=0;j<20;++j) S[j]=((enc>>j)&1)+'0';
  yy=Y;
  enc_=enc;
  return S;
}

int Answer(std::string T) {
  init();
  bigint b=from_string(T);
  vector<int>dis(100);
  for(int i=94;i>=0;--i){
    int ds=0;
    while(b>=npow[i])b-npow[i],++ds;
    dis.push_back(ds);
  }
  reverse(dis.begin(),dis.end());

  int cnt=0;
  for(ll j=0;j<(1<<7);++j){
    ll enc2 = (enc_&((1<<20)-1)) | (j<<20);
    if(enc2 == enc_) return dis[cnt];
    if(valid_enc(enc2))++cnt;
  }
  __builtin_unreachable();
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85