oj.uz

Submission #248643

# Submission time Handle Problem Language Result Execution time Memory
248643 2020-07-13T00:38:00 Z stoyan_malinin Lost in the cycle (IOI19_cycle) C++14
100 / 100
 1 ms 384 KB 
#include "cycle.h"
//#include "grader.cpp"

#include<iostream>
#include<random>
#include<time.h>

using namespace std;

mt19937 rnd(22);

struct Segment
{
    int l, r;

    Segment(){}
    Segment(int l, int r)
    {
        this->l = l;
        this->r = r;
    }

    bool isRegular()
    {
        if(l<=r) return true;
        return false;
    }
};

Segment intersect(Segment s1, Segment s2)
{
    if(s2.isRegular()==false) swap(s1, s2);

    if(s1.isRegular()==true && s2.isRegular()==true)
    {
        Segment out(max(s1.l, s2.l), min(s1.r, s2.r));
        return out;
    }
    if(s1.isRegular()==false && s2.isRegular()==false)
    {
        Segment out(max(s1.l, s2.l), min(s1.r, s2.r));
        return out;
    }

    if(s1.isRegular()==false && s2.isRegular()==true)
    {
        if(s2.l<=s1.r && s2.r>=s1.l)
        {
            cout << "MAIKA TI MRUSNA" << '\n';
        }

        if(s2.l<=s1.r) return Segment(s2.l, min(s1.r, s2.r));
        if(s2.r>=s1.l) return Segment(max(s1.l, s2.l), s2.r);

        cout << "DA IBA" << '\n';
    }

}

bool doJump(int x, int &cancelSum, int n)
{
    int xJump = (x + cancelSum)%n;
    bool res = jump(xJump);

    cancelSum = (cancelSum-xJump+n)%n;
    return res;
}

void escape(int n)
{
    int threshold = n - n/2;
    int cancelSum = 0;

    Segment ans(0, n-1);

    for(int i = 0;i<1;i++)
    {
        int x = rnd()%n;
        bool res = doJump(x, cancelSum, n);

        //cout << "ask: " << x << '\n';

        if(res==true)
        {
            if(i!=0) ans = intersect(ans, Segment((threshold - x + n)%n, (0 - x + n)%n));
            else ans = Segment((threshold - x + n)%n, (0 - x + n)%n);

            //cout << "true: " <<  (threshold - x + n)%n << " " << (0 - x + n)%n << '\n';
        }
        else
        {
            if(i!=0) ans = intersect(ans, Segment((1 - x + n)%n, (threshold - 1 - x + n)%n));
            else ans = Segment((1 - x + n)%n, (threshold - 1 - x + n)%n);

            //cout << "false: " << (1 - x + n)%n << " " << (threshold - 1 - x + n)%n << '\n';
        }

        //cout << ans.l << " -- " << ans.r << '\n';
        if(ans.isRegular()==true) break;
    }

    if(ans.l==0) ans.l++;
    if(ans.r==0) ans.r = n - 1;

    if(ans.isRegular()==false)
    {
        if(doJump(0, cancelSum, n)==true) ans.r = n - 1;
        else ans.l = 1;
    }

    int finalJump = -69;
    while(ans.l<=ans.r)
    {
        int mid = (ans.l+ans.r)/2;
        bool res = doJump(n-mid, cancelSum, n);

        if(res==true)
        {
            finalJump = n - mid;
            ans.r = mid - 1;
        }
        else
        {
            ans.l = mid + 1;
        }

        //cout << ans.l << " %% " << ans.r << " -> " << finalJump << '\n';
    }

    doJump(finalJump, cancelSum, n);

    //cout << ans.l << " " << ans.r << '\n';
}
//69696969 420

Compilation message

cycle.cpp: In function 'Segment intersect(Segment, Segment)':
cycle.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
11.0 / 11.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
56.0 / 56.0

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