Submission #248643

#	Time	Username	Problem	Language	Result	Execution time	Memory
248643		stoyan_malinin	Lost in the cycle (IOI19_cycle)	C++14	100 / 100	1 ms	384 KiB

cycle

#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 (stderr)

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 / 11
• Subtask 2: 33 / 33
• Subtask 3: 56 / 56