제출 #1312883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312883		ayaz	Rack (eJOI19_rack)	C++20	40 / 100	0 ms	332 KiB

rack

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

typedef long long ll;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 500000, inf = 1000000000, LOG = 20;
const ll mod = 1000000007, INF = 1000000000000000000;
int ans = 0, k, base, d, n;
int f(int x) {
  if (x == 1) 
    return base;
  if (x == (1LL << (n - 1)) + 1) 
    return base;
  int p = 1;
  while (p < x) p <<= 1LL;
  p >>= 1LL;
  return f(x - p) + d / p;
}
// vector<int> ans1;
// int st[sz << 2];
// void f1(int l, int r, int v) {
//   if (l == r) {
//     ans1.push_back(l);
//     st[v]++;
//     return;
//   }
//   int mid = (l + r) >> 1;
  
//   if (st[v<<1] > st[v<<1|1]) f1(mid + 1, r, v<<1|1);
//   else f1(l, mid, v<<1);

//   st[v] = st[v<<1] + st[v<<1|1];
// }
void run_case(int tc) {
  // n = rng() % 30 + 1;
  // k = rng() % (1 << n) + 1;
  // ans1.clear();
  // memset(st, 0, sizeof(st));
  // for (int i = 1; i <= k; i++)
    // f1(1, (1LL << n), 1);
  // int p = 1;
  // while (p < k) p <<= 1;
  // d = p;

  int n, k; cin >> n >> k;
  d = (1LL << (n - 1));
  n = min(60LL, n);
  if ((1LL << (n - 1)) < k) {
    base = 2;
    k -= (1LL << (n - 1));
  }
  else base = 1;
  int ans = f(k);
  cout << ans << '\n';
  // if (ans != ans1.back()) {
  //   debug(ans1, d);
  //   cout << ans1.back() << ' ' << ans << '\n';
  //   cout << n << ' ' << k << '\n';  
  //   exit(0);
  // }
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int t = 1; // e2; cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    run_case(tc);
  }
}
/*
                                                0:                              
                                               0$P:                             
                                           ~~ wPPPI:                            
                                        "~:~ .w$$$PI:  .                        
                                      v~++:  w$$P$Pcc: ~~                       
                                    !vv+::~ w$$$P$$cc: ~!~                      
                                .  cIc::::~+X$$$PP$XIc~~!+"                     
          .   .                ~. vcIo+:!+~w$$$$PP$PIIv~:+~                     
      .                   . . "v vccI+:++!c$$$$$P$$$II:!+!:..  . .... ..  .   ..
 .. ....   . .. ......... ....!:!vcIo+++!~w$$$$$$P$$Ic:!!+:~ ......... . . .. . 
............................."::+coII+!!~"$$$w$$P$$PIIv!!::~! ..................
............................!!:v+coIII~~~+!:cvP$$$PoIv~!+!+~!...................
............................:!vv~coccv~vvcvcvcwPPPPII:~!:++"+...................
............................++:v"cI::cvvvvv+v:0$P$$I:~~!!:!!!...................
............................:c!v:c!ccv::+++!!+0P$$:!~~"!!!"++...................
..."....".............~"..+.:vo:vvc:X:!+!!!!!!0P$:++"~!"+~:v!.."....."..........
...."....."........."......++vIcovv:###w!!!!!!w0+!!!"~"~~+!+...".".........."...
."""......."...".$$"."""...!:ccIowv+!#!##!!!!!!!!!!!.~!~~v+"..."..""..........."
"""""."""""""".""$B"""..."".:wvoco++!o#0R#!!!!!!!!oPPP$":~~"".".""""."."""."".""
"""".""""""+cc+""..""..."$$."+:IccI"!~!!!$$!!!!+$R+$$"~!!!"~."..""""""."."""."""
""""""""+vcIo+"""""""""""$$$#.:co~co~!!!!!!!!!:vcI:~""+!~!~"""""".""""""""""""""
""""""":cwIo+.""""""""""~$$$$ "+co"~!!~!!!!!!!!!!!".~+v!!"""""""""""""""""""""""
"""""~Icow$$$~"""@~""""..#$$#~"":cII.~"~!!!!!!!!+".:.::~"""""""""""""~"""""""""~
""""~occooI$$B""#$#""~".P:""""~"~!Ico"""~!!!!+!~.. v+!"""B"""""""""""""""~""""""
"""~~cccwc+BR~""R$$$"""""""""~"~:c"+co.""~"+~!.  v:~""""".BB""~"~~"""~""""~"""""
"~"!vcccwc".~"""R$$$$$X""""~~"~PcI".+vc."""~. .~!~~""~""~w!!R.""""~"""""""!""~""
"""!!Icwo:""""+II$$$$$$$$!""""~0$o.""~:cI... !~"""~"":+:!!+!"!X""~"""~"""!v"""""
"""".."".~~"!IIIoo!#$$$$$$$"~"~wo$$"""""~~!~~"."~"""~$""~"$$~!~"""~~"~"~:c""~""~
"...""":+~"vIIIoIc~"P$$R@$$$~"."R#P~.~""""..  ".~~~v""@~~v~~~~~"c"~~~"~:c~~"~~~~
~..~~:!!~~c$$IIo:~~~$$$@@@$$v~~.+XX~.""""""".!" ~~"~~v~c"~~~~~cI+~~~~!II+!~"~~~~
"".".":II+$R$#!~~~~$$$#@@@$$0P!~!XXv!"~"""":!!. ~~~v!P~~~~~~~vo++~~~!Ioc+~~~~~~~
".~~.!~Ico$@B$$$$$$##B@@@@$#I00wXPPXv~~~"~o0!!~~.~~~~~~~~~~~!oo+:~~!Icc!+~"~~~~~
"~!!!~!I!":!$@@@@B@B@@@@@$0c0XPwXXXXXX~~+Xww+!!~~. "~~~~~~~~voI!!~~+occ!~~~~~~~+
+"!!..""~~::~@@@@@@@@@@@R$wIXPXXXPXXXPXPcw0w~!!!~... . .~~~~~..""""wwc++~"~~~:I~
~+!.""~~~"~P@@@@@@@@@@@@R$$0$#$$XXXXXXX0X00+!+!!"... .....vv"!~~~~~IoI!~"."!oc!~
"".~""~!+XXP#@@~:+o@@@@@@@@B$$$XXXXX00Xc00I++!!!......  . cI~!!!~~!:Ic~~"".oc~"~
"~.""~~~coXP:"~~":P@@@@@BB$$#$PXXXPXX0c000+++!!!.... ... vcI"!!!!!"!vv""~~::"~++
!!"."~~~~+."~"~"~.PRBBR#w$wXXXXXXXP00oXXX+++!!!.....   . II"+~!~!!.c+:""~.!!+ww:
~!+:+.."~."""""".X0PXXX+0oXXP0P0P00XoXo0++:+!~!.........Ic!!~!!~.!!v~".""~Iow++~
"+!~:."~.~.".~"~I0XXXX~:!P0XXwXoX0oXcXo+!!+!~!"..  ... :I~!!~!~~~"!~~".~~oI!!+~"
~!+!"~~~."..""..".!+v~~~"X0XXwXcXww0I0ov++~!!... ....c:~!!!!~!~"~~.!!!~~:o!!~""~
"!!"~~~""~..."~~~.~!!.~""o0Iw".$P$$0""~II!!!... ..cv~"!!~!!~!"~~""""~!!~w:~~""".
!."!!!"~~~~~~~~~~ "~"~"".v0""###$##$#wX"v:!!!+!!!!!~!!!+~+!~~"!.""..".v:I"""~~""
"~!!~+~~~~~~~~~"~".".".++c..""$##$#P$ww""+!!!!!!!!~!!!!"~!~.~"~."~."~!:~""."""..

*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 60