Submission #1225911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225911		Godgift42	Fun Tour (APIO20_fun)	C++20	0 / 100	0 ms	836 KiB

fun

#include "fun.h"

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


std::vector<int> createFunTour(int N, int Q) {
  vector<int> per(N);
  if(N==2){
    per[0]=0;
    per[1]=1;
    return per;
  }
  int cnt=0;
  int cur=0;
  int cn=N;
  vector<int> sp(100001);
  int ff=3;
  int fg=1;
  while(ff<=100000){
    sp[ff]=fg;
    fg=fg*2+2;
    ff=ff*2+1;
  }
  while(cnt<N){
    vector<int> bf1;
    vector<int>bf2;
    queue<int> q;
    if(cur*2+2>=cn){
      if(cur*2+1>=cn){
        per[cnt]=cur;
        cnt++;
      }
      else{
        per[cnt]=cur*2+1;
        cnt++;
        per[cnt]=cur;
        cnt++;
      }
      break;
    }
    q.push(cur*2+2);
    while(!q.empty()){
      int u=q.front();
      bf2.push_back(u);
      q.pop();
      if(u*2+1<cn)q.push(u*2+1);
      if(u*2+2<cn)q.push(u*2+2);
    }
    reverse(bf2.begin(),bf2.end());
    if(bf2[0]==cn-1){
      q.push(cur*2+1);
      while(!q.empty()){
        int u=q.front();
        bf1.push_back(u);
        q.pop();
        if(u*2+1<cn)q.push(u*2+1);
        if(u*2+2<cn)q.push(u*2+2);
      }
      reverse(bf1.begin(),bf1.end());
      bf1.push_back(cur);
      int i=0;
      int j=0;
      bool ch=false;
      while(cnt<N){
        per[cnt]=bf1[i];
        i++;
        cnt++;
        if(cnt==N)break;
        if(!ch){
          per[cnt]=bf2[j];
          j++;
          cnt++;
          if(j==bf2.size()){
            ch=true;
            j=bf1.size()-1;
          }
        }
        else{
          per[cnt]=bf1[j];
          j--;
          cnt++;
        }
      }
    }
    else{
      bf2.push_back(cur);
      for(int j=0;j<bf2.size();j++){
        per[cnt]=cn-1;
        if(sp[cn-1]!=0){
          cn=sp[cn-1]+2;
        }
        cn--;
        cnt++;
        per[cnt]=bf2[j];
        cnt++;
      }
      cur=2*cur+1;
    }
  }
  return per;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34