Submission #1008369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008369		oolimry	City (JOI17_city)	C++17	8 / 100	219 ms	52432 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

#define maxn 250005
int pre[maxn],pst[maxn],cnt;
vector<int> seq,AL[maxn];

void build(){
  const long double factor = 2;
  seq.pb(0);seq.pb(1);
  for(int i=2;i<21;++i){
    int x=(int)(factor*seq.back());
    if(x==seq.back())++x;
    seq.pb(x);
  }
}

void dfs(int u){
  pre[u]=cnt++;
  for(int v:AL[u]){
    if(pre[v]==-1)dfs(v);
  }
  int pos=lower_bound(all(seq),cnt-pre[u])-seq.begin();
  cnt+=seq[pos]+pre[u]-cnt;
  pst[u]=cnt-1;
}

void Encode(int n,int a[],int b[]){
  build();
  memset(pre,-1,sizeof pre);
  for(int i=0;i<n-1;++i){
    AL[a[i]].pb(b[i]);
    AL[b[i]].pb(a[i]);
  }
  dfs(0);
  //for(int i=0;i<n;++i)pf("%d %d\n",pre[i],pst[i]);
  for(int i=0;i<n;++i){
    int dist=pst[i]-pre[i]+1;
    int x=lower_bound(all(seq),dist)-seq.begin();
    assert(x<sz(seq)&&seq[x]==dist);
    Code(i,(1ll<<20)*x+pre[i]);
  }
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

int ones=(1<<20)-1;

vector<int> seq2;

void build2(){
  const long double factor = 2;
  seq2.pb(0);seq2.pb(1);
  for(int i=2;i<21;++i){
    int x=(int)(factor*seq2.back());
    if(x==seq2.back())++x;
    seq2.pb(x);
  }
}

void InitDevice(){
  build2();
}

int Answer(ll S, ll T){
  ll preS=S&ones,preT=T&ones;
  ll distS=S>>20,distT=T>>20;
  ll pstS=preS+seq2[distS]-1,pstT=preT+seq2[distT]-1;
  //pf("S: %lld %lld %lld\n",preS,distS,pstS);
  //pf("T: %lld %lld %lld\n",preT,distT,pstT);
  if(preT<=preS&&preS<=pstT)return 0;
  if(preS<=preT&&preT<=pstS)return 1;
  return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92