Submission #222138

#	Time	Username	Problem	Language	Result	Execution time	Memory
222138		TheLorax	Building 4 (JOI20_building4)	C++11	11 / 100	2104 ms	356164 KiB

building4

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LBS 20
#define MOD ((ll)1224736769)//((ll)((1<<24)+(1<<16)+(1<<8)+1))//((long long)1e9+7) //1e9+9
#define PHIMOD ((ll)MOD-1) //((ll)(1<<24))
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef int64_t ll;
typedef double rat;
typedef long long bi;
typedef pair<ll, ll> ii;
typedef std::vector<ii> vii;
typedef std::map<ll, ll> mii;
typedef bitset<LBS> bis;
typedef std::vector<bis> vbs;
typedef array<std::vector<ll>, 4> av; //aa,ab,ba,bb

template<class T>
void in(T &a){
  for(auto &x: a)
    cin >> x;
}

template<class T>
void out(T &a, string sep=" "){
  for(auto x: a)
    cout << x<<sep;
  cout << '\n';
}

template<class T>
void err(T &a, string sep=" "){
  for(auto x: a)
    cerr << x <<sep;
  cerr << '\n';
}

std::vector<std::vector<int> > mp;
ll np2=1, fa;
std::vector<ll> pa;
map<ii,av> miiav;

void fft(std::vector<ll> &v, std::vector<ll> &f, int n, int in){
  for(int i=0; i<n; i++)
    f[i]=v[mp[__builtin_ctz(n)][i]];
  ll t;
  for(int l=1; l<n; l*=2)
    for(int st=0; st<n; st+=l*2)
      for(int i=0; i<l; i++){
        t=f[st+i];
        f[st+i]=(t+(pa[(np2+in*i*np2/l/2)%np2]*f[st+i+l])%MOD+MOD)%MOD;
        f[st+i+l]=(t+(pa[(np2+in*(i+l)*np2/l/2)%np2]*f[st+i+l])%MOD+MOD)%MOD;
      }
}

void fftsparse(std::vector<ll> &v, std::vector<ll> &f, int n, char in){
  for(int i=0; i<n; i++){
    f[i]=0;
    for(auto x: v)
      f[i]+=pa[(np2+in*(np2/n*x)%np2*i)%np2];
  }
}


void rek(const av &a, av &v, int st=0, int l=np2){
  if(l==1){
    v[0][0]=v[3][0]=1;
    miiav[{st,l}][0].PB(0);
    miiav[{st,l}][3].PB(0);
    return;
  }
  miiav[{st,l}][0].clear();
  if(l==2){
    miiav[{st,1}][0].PB(0);
    miiav[{st,1}][3].PB(0);
    miiav[{st+1,1}][0].PB(0);
    miiav[{st+1,1}][3].PB(0);
    for(int k=0; k<4; k++)
      if (a[k/2][st]<=a[k%2][st+1]) {
        v[k][1-k/2]=1;
        miiav[{st,l}][k].PB(1-k/2);
      }
    return;
  }
  av lv, rv, lf, rf;
  for(int i=0; i<4; i++){
    lv[i].resize(l,0);
    rv[i].resize(l,0);
    lf[i].resize(l);
    rf[i].resize(l);
  }
  rek(a,lv,st,l/2);
  rek(a,rv,st+l/2,l/2);

  for(int i=0; i<4; i++){
    if(0 && SZ((miiav[{st,l/2}][i]))<__builtin_ctz(l)*2+3)
      fftsparse(miiav[{st,l/2}][i],lf[i],l,1);
    else
      fft(lv[i], lf[i], l, 1);
    if(0 && SZ((miiav[{st+l/2,l/2}][i]))<__builtin_ctz(l)*2+3)
      fftsparse(miiav[{st+l/2,l/2}][i],rf[i],l,1);
    else
      fft(rv[i], rf[i], l, 1);
  }
  av f;
  for(int j=0; j<4; j++){
    f[j].resize(l,0);
    for(int k=0; k<4; k++)
      if(a[k/2][st+l/2-1]<=a[k%2][st+l/2])
        for(int i=0; i<l; i++)
          f[j][i]+=(lf[(j/2)*2+k/2][i]*((rf[(k%2)*2+j%2][i]*(k/2?1:pa[(np2/l*i)%np2]))%MOD))%MOD;
  }
  for(int i=0; i<4; i++){
    fft(f[i],v[i],l, -1);
    for(int j=0; j<l; j++)
      if(v[i][j]){
        v[i][j]=1;
        miiav[{st,l}][i].PB(j);
      }
  }
}

void path(const av &a, char* s, int an, int dir, int st=0, int l=np2){
  if(l==1){
    assert(dir==0 || dir==3);
    s[st]=(dir==0?'A':'B');
    return;
  }
  assert(miiav.count({st,l/2}) && miiav.count({st+l/2,l/2}));
  const av &le=miiav[{st,l/2}], &ri=miiav[{st+l/2, l/2}];
  // err(lv);
  for(int k=0; k<4; k++)
    if(a[k/2][st+l/2-1]<=a[k%2][st+l/2]){
      int il=0, ir=SZ(ri[(k%2)*2+dir%2])-1;
      while (il<SZ(le[(dir/2)*2+k/2]) && ir>=0) {
        int at=le[(dir/2)*2+k/2][il]+(1-k/2)+ri[(k%2)*2+dir%2][ir];
        if(at==an){
          path(a,s,le[(dir/2)*2+k/2][il],(dir/2)*2+k/2,st,l/2);
          path(a,s,ri[(k%2)*2+dir%2][ir],(k%2)*2+dir%2,st+l/2,l/2);
          return;
        } if(at<an)
          il++;
        else
         ir--;
      }
    }
      //
      // for(int i=max((1-k/2),an-l); i<=min(an,l+(1-k/2)); i++)
      //   if(lv[(dir/2)*2+k/2][i-(1-k/2)] && rv[(k%2)*2+dir%2][an-i]){
      //     path(a,s,i-(1-k/2),(dir/2)*2+k/2,st,l/2);
      //     path(a,s,an-i,(k%2)*2+dir%2,st+l/2,l/2);
      //     return;
      //   }
  assert(1);
}

int main(){
  int n; scanf("%d", &n);
  n*=2;
  while(np2<n)
    np2*=2;
  av a;
  for(int i=0; i<2; i++){
    a[i].resize(n);
    for(int j=0; j<n; j++)
      scanf("%lld", &a[i][j]);
    a[i].resize(np2);
  }
  for(int i=n; i<np2; i++){
    a[0][i]=a[0][n-1]+a[1][n-1];
    a[1][i]=0;
  }

  fa=1;
  for(int i=0; i<73; i++)
    fa=(fa*3)%MOD;
  for(int i=1; i<PHIMOD/73/np2; i*=2)
    fa=(fa*fa)%MOD;

  pa.resize(np2+1);
  pa[0]=1;
  for(int i=1; i<=np2; i++)
    pa[i]=(pa[i-1]*fa)%MOD;

  mp.resize(__builtin_ctz(np2)+1);
  mp[0].resize(1);
  mp[0][0]=0;
  for(int i=1; i<SZ(mp); i++){
    mp[i].resize(1<<i);
    for(int j=0; j<(1<<(i-1)); j++)
      mp[i][j]=mp[i-1][j]*2;
    for(int j=0; j<(1<<(i-1)); j++)
      mp[i][j+(1<<(i-1))]=mp[i-1][j]*2+1;
  }

  av v;
  for(int i=0; i<4; i++)
    v[i].resize(np2,0);
  rek(a,v);
  for(int i=0; i<4; i++)
    if(v[i][np2-n/2-(1-i%2)]){
      char s[np2*2];
      path(a,s,np2-n/2-(1-i%2),i);
      s[n]=0;
      printf("%s\n", s);
      return 0;
    }
  printf("-1\n");
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:181:29: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long int> >::value_type* {aka long int*}' [-Wformat=]
       scanf("%lld", &a[i][j]);
                             ^
building4.cpp:173:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int n; scanf("%d", &n);
          ~~~~~^~~~~~~~~~
building4.cpp:181:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &a[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89