oj.uz

Submission #811033

# Submission time Handle Problem Language Result Execution time Memory
811033 2023-08-06T21:43:28 Z cjoa Lost in the cycle (IOI19_cycle) C++17
100 / 100
 1 ms 208 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct
20 Correct 0 ms 208 KB Output is correct
21 Correct 0 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 0 ms 208 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 0 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct
20 Correct 0 ms 208 KB Output is correct
21 Correct 0 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 0 ms 208 KB Output is correct
24 Correct 0 ms 208 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 0 ms 208 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 0 ms 208 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 0 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Correct 0 ms 208 KB Output is correct
35 Correct 0 ms 208 KB Output is correct
36 Correct 0 ms 208 KB Output is correct
37 Correct 0 ms 208 KB Output is correct
38 Correct 1 ms 208 KB Output is correct
39 Correct 1 ms 208 KB Output is correct
40 Correct 0 ms 208 KB Output is correct
41 Correct 1 ms 208 KB Output is correct
42 Correct 0 ms 208 KB Output is correct
43 Correct 1 ms 208 KB Output is correct
44 Correct 0 ms 208 KB Output is correct
45 Correct 1 ms 208 KB Output is correct
46 Correct 0 ms 208 KB Output is correct
47 Correct 0 ms 208 KB Output is correct
48 Correct 1 ms 208 KB Output is correct
49 Correct 0 ms 208 KB Output is correct
50 Correct 0 ms 208 KB Output is correct
51 Correct 1 ms 208 KB Output is correct
52 Correct 0 ms 208 KB Output is correct
53 Correct 1 ms 208 KB Output is correct
54 Correct 1 ms 208 KB Output is correct
55 Correct 1 ms 208 KB Output is correct
56 Correct 0 ms 208 KB Output is correct
57 Correct 1 ms 208 KB Output is correct
58 Correct 0 ms 208 KB Output is correct
59 Correct 1 ms 208 KB Output is correct
60 Correct 1 ms 208 KB Output is correct
61 Correct 0 ms 208 KB Output is correct