Submission #1317300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317300		Tymond	A Light Inconvenience (CEOI23_light)	C++20	100 / 100	177 ms	440 KiB

light

#include "light.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

ll n;
vll curr = {};

void prepare(){
    n = 1LL;
    curr = {1LL};
}

ll getX(ll P){
    if((n - P) & 1LL){
        return (n - P) / 2LL;
    }else{
        return (n - P) / 2LL - 1;
    }
}

//obie funkcje zwracają (p, ncurr)
pair<ll, vll> join(ll p){
    n += p;
    vector<pll> intervals;
    int i = 0;
    while(i < sz(curr)){
        int pocz = i;
        while(i + 1 < sz(curr) && curr[i] + p >= curr[i + 1] - 1){
            i++;
        }
        intervals.pb(mp(max(2LL, curr[pocz]), min(n, curr[i] + p)));
        i++;
    }

    // cerr << "JOINING: " << p << '\n';
    // cerr << n << '\n';
    // debug(curr);
    // for(auto ele : intervals){
    //     cerr << ele << '\n';
    // }
    vll ncurr = {1LL};
    ll P = 1LL;
    int wsk = 0;
    while(true){
        ll x = getX(P);
       // cerr << x << ' ' << P << '\n';
        if(x <= 0LL){
            break;
        }
        while(wsk + 1 < sz(intervals) && intervals[wsk + 1].fi <= n - x){
            wsk++;
        }
        //musi być coś w przedziale [n - 2 * x, n - x]
        P = min(intervals[wsk].se, n - x);
        ncurr.pb(P);
    }
    if(ncurr.back() != n){
        ncurr.pb(n);
    }

    curr = ncurr;
    //debug(curr);
    return mp(p, ncurr);
}

pair<ll, vll> leave(ll p){
    n -= p;
    vector<pll> intervals;
    int i = 0;
    while(i < sz(curr)){
        if(curr[i] > n){
            break;
        }
        int pocz = i;
        while(i + 1 < sz(curr) && curr[i] + p >= curr[i + 1] - 1){
            i++;
        }
        intervals.pb(mp(max(2LL, curr[pocz]), min(n, curr[i] + p)));
        //cerr << max(2LL, curr[pocz]) << ' ' << min(n, curr[i] + p) << '\n';
        if(curr[i] + p > n){
            break;
        }
        i++;
    }

    // cerr << "LEAVING: " << p << '\n';
    // cerr << n << '\n';
    // debug(curr);
    // for(auto ele : intervals){
    //     cerr << ele << '\n';
    // }
    vll ncurr = {1LL};
    ll P = 1LL;
    int wsk = 0;
    while(true){
        ll x = getX(P);
        //cerr << x << ' ' << P << '\n';
        if(x <= 0LL){
            break;
        }
        while(wsk + 1 < sz(intervals) && intervals[wsk + 1].fi <= n - x){
            wsk++;
        }
        //musi być coś w przedziale [n - 2 * x, n - x]
        P = min(intervals[wsk].se, n - x);
        ncurr.pb(P);
    }
    if(ncurr.back() != n){
        ncurr.pb(n);
    }

    curr = ncurr;
   // debug(curr);
    return mp(p, ncurr);
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 5 / 5
• Subtask 7: 60 / 60