oj.uz

답안 #1008145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008145 2024-06-26T07:57:55 Z GrindMachine Flight to the Ford (BOI22_communication) C++17
74 / 100
 3116 ms 3616 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(n);
    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(n);
    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 7 ms 2860 KB Output is correct
2 Correct 8 ms 2760 KB Output is correct
3 Correct 10 ms 2832 KB Output is correct
4 Correct 6 ms 2764 KB Output is correct
5 Correct 11 ms 2740 KB Output is correct
6 Correct 18 ms 2900 KB Output is correct
7 Correct 34 ms 2936 KB Output is correct

Subtask #2
59.00003 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 612 ms 3616 KB Output is partially correct
2 Partially correct 345 ms 2864 KB Output is partially correct
3 Partially correct 442 ms 3044 KB Output is partially correct
4 Partially correct 652 ms 2992 KB Output is partially correct
5 Partially correct 530 ms 2848 KB Output is partially correct
6 Partially correct 442 ms 3020 KB Output is partially correct
7 Partially correct 1938 ms 3000 KB Output is partially correct
8 Partially correct 3010 ms 3220 KB Output is partially correct
9 Partially correct 2661 ms 3472 KB Output is partially correct
10 Partially correct 2806 ms 3156 KB Output is partially correct
11 Partially correct 2672 ms 3304 KB Output is partially correct
12 Partially correct 2512 ms 3436 KB Output is partially correct
13 Partially correct 2672 ms 3508 KB Output is partially correct
14 Partially correct 2635 ms 2944 KB Output is partially correct
15 Partially correct 1408 ms 3172 KB Output is partially correct
16 Partially correct 3116 ms 3244 KB Output is partially correct
17 Partially correct 614 ms 2972 KB Output is partially correct
18 Partially correct 692 ms 3232 KB Output is partially correct
19 Partially correct 689 ms 3244 KB Output is partially correct
20 Partially correct 633 ms 3140 KB Output is partially correct
21 Partially correct 733 ms 3224 KB Output is partially correct
22 Partially correct 770 ms 2980 KB Output is partially correct
23 Partially correct 1093 ms 2976 KB Output is partially correct
24 Correct 5 ms 2744 KB Output is correct
25 Correct 8 ms 3004 KB Output is correct
26 Correct 12 ms 2764 KB Output is correct
27 Correct 4 ms 2884 KB Output is correct
28 Correct 9 ms 2760 KB Output is correct
29 Correct 19 ms 3168 KB Output is correct
30 Correct 29 ms 2724 KB Output is correct