oj.uz

답안 #1008150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008150 2024-06-26T07:59:19 Z GrindMachine Flight to the Ford (BOI22_communication) C++17
74 / 100
 2975 ms 3808 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read some solutions a long time ago, remember some key ideas from there

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "communication.h"
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
//     communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//

void encode(int n, int k) {
    int currn = 1;
    while(currn <= n){
        currn <<= 1;
    }

    n = currn;
    mt19937 rng((ll)n*100+5);
    int xo = rng()%n;
    k--;
    k ^= xo;
    k++;

    vector<int> a = {0,6,9,15};
    vector<vector<int>> possible(4);

    rep(i,4){
        int x = a[i];
        rep(mask,1<<4){
            int pb = -1;
            bool ok = true;

            rep(bit,4){
                int b = 0;
                if(mask&(1<<bit)) b = 1;
                if(b == 1 and pb == 1){
                    ok = false;
                }
                pb = b;
            }

            if(ok){
                possible[i].pb(x^mask);
            }
        }
    }

    map<int,int> mp;
    mp[1] = 0, mp[n+1] = 0;

    auto range_add = [&](int l, int r, int x){
        mp[l] += x, mp[r+1] -= x;
    };

    auto cnt_zero = [&](){
        vector<pii> b(all(mp));
        int sum = 0;
        int cnt = 0;

        rep(i,sz(b)-1){
            sum += b[i].ss;
            if(sum == 0){
                int len = b[i+1].ff-b[i].ff;
                cnt += len;        
            }    
        }

        return cnt;
    };

    auto kth_zero = [&](int k){
        vector<pii> b(all(mp));
        int sum = 0;

        rep(i,sz(b)-1){
            sum += b[i].ss;
            if(sum == 0){
                int len = b[i+1].ff-b[i].ff;
                if(k <= len){
                    return b[i].ff+k-1;
                }
                else{
                    k -= len;
                }
            }    
        }

        assert(0);
        return -1;
    };

    auto my_send = [&](int i){
        int x = a[i], y = 0;
        rep(bit,4){
            int b = 0;
            if(x&(1<<bit)) b = 1;
            int sent = send(b);
            y |= sent*(1<<bit);
        }
        
        return y;
    };

    while(true){
        int active = cnt_zero();
        if(active <= 2) break;

        vector<int> lens;
        int s1 = active/4, c1 = 4;
        int s2 = ceil2(active,4), c2 = active%4;
        c1 -= c2;
        rep(i,c1) lens.pb(s1);
        rep(i,c2) lens.pb(s2);
        vector<pii> ranges;
        int z = 0;

        rep(i,4){
            int len = lens[i];
            if(!len){
                ranges.pb({0,0});
            }    
            else{
                int l = kth_zero(z+1), r = kth_zero(z+len);
                z += len;
                ranges.pb({l,r});
            }
        }

        int to_send = -1;

        rep(i,4){
            auto [l,r] = ranges[i];
            if(l <= k and r >= k){
                to_send = i;
            }
        }

        int x = my_send(to_send);

        vector<int> bad;
        rep(i,4){
            if(!count(all(possible[i]),x)){
                bad.pb(i);
            }
        }

        trav(i,bad){
            if(ranges[i].ff == -1) conts;
            range_add(ranges[i].ff,ranges[i].ss,1);
        }
    }
}

std::pair<int, int> decode(int n) {
    int currn = 1;
    while(currn <= n){
        currn <<= 1;
    }

    int on = n;
    n = currn;
    mt19937 rng((ll)n*100+5);
    int xo = rng()%n;

    vector<int> a = {0,6,9,15};
    vector<vector<int>> possible(4);

    rep(i,4){
        int x = a[i];
        rep(mask,1<<4){
            int pb = -1;
            bool ok = true;

            rep(bit,4){
                int b = 0;
                if(mask&(1<<bit)) b = 1;
                if(b == 1 and pb == 1){
                    ok = false;
                }
                pb = b;
            }

            if(ok){
                possible[i].pb(x^mask);
            }
        }
    }

    map<int,int> mp;
    mp[1] = 0, mp[n+1] = 0;

    auto range_add = [&](int l, int r, int x){
        mp[l] += x, mp[r+1] -= x;
    };

    auto cnt_zero = [&](){
        vector<pii> b(all(mp));
        int sum = 0;
        int cnt = 0;

        rep(i,sz(b)-1){
            sum += b[i].ss;
            if(sum == 0){
                int len = b[i+1].ff-b[i].ff;
                cnt += len;        
            }    
        }

        return cnt;
    };

    auto kth_zero = [&](int k){
        vector<pii> b(all(mp));
        int sum = 0;

        rep(i,sz(b)-1){
            sum += b[i].ss;
            if(sum == 0){
                int len = b[i+1].ff-b[i].ff;
                if(k <= len){
                    return b[i].ff+k-1;
                }
                else{
                    k -= len;
                }
            }    
        }

        assert(0);
        return -1;
    };

    auto my_receive = [&](){
        int x = 0;
        rep(bit,4){
            x = x<<1|receive();
        }
        return x;
    };

    while(true){
        int active = cnt_zero();
        if(active <= 2) break;

        vector<int> lens;
        int s1 = active/4, c1 = 4;
        int s2 = ceil2(active,4), c2 = active%4;
        c1 -= c2;
        rep(i,c1) lens.pb(s1);
        rep(i,c2) lens.pb(s2);
        vector<pii> ranges;
        int z = 0;

        rep(i,4){
            int len = lens[i];
            if(!len){
                ranges.pb({0,0});
            }    
            else{
                int l = kth_zero(z+1), r = kth_zero(z+len);
                z += len;
                ranges.pb({l,r});
            }
        }

        int x = my_receive();

        vector<int> bad;
        rep(i,4){
            if(!count(all(possible[i]),x)){
                bad.pb(i);
            }
        }

        trav(i,bad){
            if(ranges[i].ff == -1) conts;
            range_add(ranges[i].ff,ranges[i].ss,1);
        }
    }

    int active = cnt_zero();
    pii res = {0,0};
    res.ff = kth_zero(1);
    res.ss = res.ff;

    if(active == 2){
        res.ss = kth_zero(2);
    }

    res.ff--, res.ss--;
    res.ff ^= xo, res.ss ^= xo;
    res.ff++, res.ss++;

    if(res.ff > on) res.ff = 1;
    if(res.ss > on) res.ss = 1;

    return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2740 KB Output is correct
2 Correct 13 ms 2736 KB Output is correct
3 Correct 7 ms 2764 KB Output is correct
4 Correct 13 ms 2656 KB Output is correct
5 Correct 12 ms 2748 KB Output is correct
6 Correct 16 ms 3076 KB Output is correct
7 Correct 30 ms 2720 KB Output is correct

Subtask #2
59.00003 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 556 ms 2832 KB Output is partially correct
2 Partially correct 281 ms 2832 KB Output is partially correct
3 Partially correct 400 ms 2748 KB Output is partially correct
4 Partially correct 692 ms 2776 KB Output is partially correct
5 Partially correct 594 ms 2848 KB Output is partially correct
6 Partially correct 536 ms 2976 KB Output is partially correct
7 Partially correct 1890 ms 2992 KB Output is partially correct
8 Partially correct 2970 ms 3128 KB Output is partially correct
9 Partially correct 2550 ms 3068 KB Output is partially correct
10 Partially correct 2543 ms 3408 KB Output is partially correct
11 Partially correct 2594 ms 3808 KB Output is partially correct
12 Partially correct 2687 ms 3648 KB Output is partially correct
13 Partially correct 2790 ms 3788 KB Output is partially correct
14 Partially correct 2698 ms 2932 KB Output is partially correct
15 Partially correct 1414 ms 3028 KB Output is partially correct
16 Partially correct 2975 ms 3116 KB Output is partially correct
17 Partially correct 721 ms 2976 KB Output is partially correct
18 Partially correct 770 ms 3128 KB Output is partially correct
19 Partially correct 663 ms 2976 KB Output is partially correct
20 Partially correct 675 ms 3444 KB Output is partially correct
21 Partially correct 758 ms 3232 KB Output is partially correct
22 Partially correct 728 ms 2968 KB Output is partially correct
23 Partially correct 1168 ms 2968 KB Output is partially correct
24 Correct 5 ms 2768 KB Output is correct
25 Correct 7 ms 2752 KB Output is correct
26 Correct 11 ms 3012 KB Output is correct
27 Correct 6 ms 2736 KB Output is correct
28 Correct 11 ms 2872 KB Output is correct
29 Correct 20 ms 3036 KB Output is correct
30 Correct 25 ms 2768 KB Output is correct