Submission #515654

# Submission time Handle Problem Language Result Execution time Memory
515654 2022-01-19T12:15:07 Z LouayFarah Uzastopni (COCI17_uzastopni) C++14
80 / 80
12 ms 312 KB
#include "bits/stdc++.h"

using namespace std;

#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const long long MOD = 998244353;
const long long INF = 1e18;

int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};

ll my_rand(ll l, ll r)
{
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ll len = r-l;
    ll a = rand()%len;
    ll b = rand()%len;

    ll res = ((((a%len)*((RAND_MAX+1)%len))%len) + (b%len))%len;

    if(res<l)
        res +=l;

    return res;
}

bool f(ll mid, ll len, ll n)
{
    ll sum = (2*mid + len-1)*len;
    sum/=2;

    //cout << sum << endl;

    if(sum<=n)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    ll n;
    cin >> n;

    ll lim = 2*int(sqrt(n + .0)) +10;

    for(int len = 2; len<=lim; len++)
    {
        ll l = 1, r = 1;
        while(f(r, len, n))
            r*=2;

        while(l+1<r)
        {
            ll mid = (l+r)/2;

            if(f(mid, len, n))
                l = mid;
            else
                r = mid;
        }

        ll sum = (2*l+len-1)*len;
        sum/=2;

        if(sum==n)
        {
            cout << l << ' ' << l+len-1 << endl;
        }
    }

    return 0;
}

Compilation message

uzastopni.cpp: In function 'long long int my_rand(long long int, long long int)':
uzastopni.cpp:25:35: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   25 |     ll res = ((((a%len)*((RAND_MAX+1)%len))%len) + (b%len))%len;
      |                                   ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 204 KB Output is correct
10 Correct 12 ms 312 KB Output is correct