Submission #1122871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122871		Bolatulu	Flight to the Ford (BOI22_communication)	C++20	0 / 100	267 ms	2800 KiB

communication

// Bolatulu
#include <bits/stdc++.h>
#include "communication.h"

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/

typedef long long ll;
typedef unsigned long long ull; 
typedef double db;
#define pb push_back
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,md
#define TR v+v+1,md+1,tr
#define Tl t[v].l,tl,md
#define Tr t[v].r,md+1,tr
#define all(x) (x).begin(),(x).end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
// #define int long long
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define ld long double
using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18+7;
const int N = 1e5+7;
const int M = 1e4+7;
const ld eps = 1e-3;

pair <int,int> calc(int a,int b,int c,int d) {
    if (b==c) {
        if (b)
            return {1,3};
        return {2,-1};
    }
    if (a==d) {
        if (a)
            return {1,3};
        return {1,-1};
    }
    if (a==b)
        return {3,-1};
    return {1,-1};
}

void encode(int n,int x) {
    int m=n;
    deque <pair <int,int>> v={{1,n}};
    while (m>2) {   
        deque <pair <int,int>> v1,v2,v3;
        int m1=m/3,m2=m/3,m3=m/3;
        if (m%3>0)
            m3++;
        if (m%3>1)
            m2++;
        while (!v.empty() and v[0].S-v[0].F+1<=m1) {
            m1-=v[0].S-v[0].F+1;
            v1.pb(v[0]);
            v.pop_front();
        }
        if (m1>0) {
            int l=v[0].F,r=v[0].S;
            v1.eb(l,l+m1-1);
            v.pop_front();
            v.push_front({l+m1,r});
            m1=0;
        }
        while (!v.empty() and v[0].S-v[0].F+1<=m2) {
            m2-=v[0].S-v[0].F+1;
            v2.pb(v[0]);
            v.pop_front();
        }
        if (m2>0) {
            int l=v[0].F,r=v[0].S;
            v2.eb(l,l+m2-1);
            v.pop_front();
            v.push_front({l+m2,r});
            m2=0;
        }
        while (!v.empty() and v[0].S-v[0].F+1<=m3) {
            m3-=v[0].S-v[0].F+1;
            v3.pb(v[0]);
            v.pop_front();
        }
        bool ok1=false,ok2=false;
        for (auto now : v1) {
            if (x>=now.F and x<=now.S)
                ok1=true;
        }
        for (auto now : v2) {
            if (x>=now.F and x<=now.S)
                ok2=true;
        }
        pair <int,int> z=calc(send(ok1),send(ok2),send(ok2),send(ok1));
        m1=m/3,m2=m/3,m3=m/3;
        if (m%3>0)
            m3++;
        if (m%3>1)
            m2++;
        if (z.F==1) {
            m-=m1;
            v1.clear();
        } else if (z.F==2) {
            m-=m2;
            v2.clear();
        } else {
            m-=m3;
            v3.clear();
        }
        if (z.S==1) {
            m-=m1;
            v1.clear();
        } else if (z.S==2) {
            m-=m2;
            v2.clear();
        } else if (z.S==3) {
            m-=m3;
            v3.clear();
        }
        v=v1;
        v.ins(v.end(),all(v2));
        v.ins(v.end(),all(v3));
    }
}

pair <int,int> decode(int n) {
    int m=n;
    deque <pair <int,int>> v={{1,n}};
    while (m>2) {   
        deque <pair <int,int>> v1,v2,v3;
        int m1=m/3,m2=m/3,m3=m/3;
        if (m%3>0)
            m3++;
        if (m%3>1)
            m2++;
        while (!v.empty() and v[0].S-v[0].F+1<=m1) {
            m1-=v[0].S-v[0].F+1;
            v1.pb(v[0]);
            v.pop_front();
        }
        if (m1>0) {
            int l=v[0].F,r=v[0].S;
            v1.eb(l,l+m1-1);
            v.pop_front();
            v.push_front({l+m1,r});
            m1=0;
        }
        while (!v.empty() and v[0].S-v[0].F+1<=m2) {
            m2-=v[0].S-v[0].F+1;
            v2.pb(v[0]);
            v.pop_front();
        }
        if (m2>0) {
            int l=v[0].F,r=v[0].S;
            v2.eb(l,l+m2-1);
            v.pop_front();
            v.push_front({l+m2,r});
            m2=0;
        }
        while (!v.empty() and v[0].S-v[0].F+1<=m3) {
            m3-=v[0].S-v[0].F+1;
            v3.pb(v[0]);
            v.pop_front();
        }
        pair <int,int> z=calc(receive(),receive(),receive(),receive());
        m1=m/3,m2=m/3,m3=m/3;
        if (m%3>0)
            m3++;
        if (m%3>1)
            m2++;
        if (z.F==1) {
            m-=m1;
            v1.clear();
        } else if (z.F==2) {
            m-=m2;
            v2.clear();
        } else {
            m-=m3;
            v3.clear();
        }
        if (z.S==1) {
            m-=m1;
            v1.clear();
        } else if (z.S==2) {
            m-=m2;
            v2.clear();
        } else if (z.S==3) {
            m-=m3;
            v3.clear();
        }
        v=v1;
        v.ins(v.end(),all(v2));
        v.ins(v.end(),all(v3));
    }
    return {v[0].F,v[1].F};
}

/*
signed main() {
    // file("jenga");
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int test = 1;
    solve(3);
    // cin >> test;
    while (test--) {
        // solve();
        if (test)
            cout << '\n';
    }
    return 0;
}
*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85