Submission #811033

#	Time	Username	Problem	Language	Result	Execution time	Memory
811033		cjoa	Lost in the cycle (IOI19_cycle)	C++17	100 / 100	1 ms	208 KiB

cycle

#include "cycle.h"
#include <bits/stdc++.h>

using namespace std;

int cnt_jump = 0;
bool my_jump(int x) {
   ++cnt_jump;
//   cout << "Salto #" << cnt_jump << " x = " << x << endl;
   bool res = jump(x);
   return res;
}

void escape(int n) {
   cnt_jump = 0;

   if (n == 2) {
      my_jump(1);
      return;
   }

   bool flag = my_jump(0);

   if (!flag) {
      // inicialmente, estoy en la zona de F

      int lo = 1, hi = n/2;
//      if (n % 2 == 0) hi = n / 2 - 1;
//      else hi = n / 2;

      bool salto_anterior_verdadero = false;
      int salto_anterior = 0;
      while (lo <= hi) {
         int mid = lo + (hi - lo) / 2;
         int x;
         if (salto_anterior_verdadero)
            x = n - salto_anterior + mid;
         else
            x = mid - salto_anterior;
         if (my_jump(x)) {
            hi = mid - 1;
            salto_anterior_verdadero = true;
         }
         else {
            lo = mid + 1;
            salto_anterior_verdadero = false;
         }
         salto_anterior = mid;
      }
      if (salto_anterior_verdadero)
         my_jump(n / 2);
      else
         my_jump(n / 2 + 1);
   }
   else {
      // inicialmente, estoy en la zona de T

      int lo = 1, hi = n/2;

      bool salto_anterior_verdadero = false;
      int salto_anterior = 0;
      while (lo <= hi) {
         int mid = lo + (hi - lo) / 2;
         int x;
         if (salto_anterior_verdadero)
            x = n - salto_anterior + mid;
         else
            x = mid - salto_anterior;
         x %= n;
         if (x < 0) x += n;
         if (my_jump(x)) {
            lo = mid + 1;
            salto_anterior_verdadero = true;
         }
         else {
            hi = mid - 1;
            salto_anterior_verdadero = false;
         }
         salto_anterior = mid;
      }
      if (salto_anterior_verdadero) {
         // no tengo que saltar
      }
      else
         my_jump(n - 1);
   }
}

• Subtask 1: 11 / 11
• Subtask 2: 33 / 33
• Subtask 3: 56 / 56