oj.uz

Submission #900630

# Submission time Handle Problem Language Result Execution time Memory
900630 2024-01-08T17:36:54 Z GrindMachine Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 49 ms 10652 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(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-773760
edi

*/

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

typedef __int128 big;

void my_print(big x){
    string s = "";
    while(x){
        s.pb(char('0'+x%10));
        x /= 10;
    }
    reverse(all(s));
    cout << s << endl;
}

#include "Anna.h"

void Anna(int n, std::vector<char> A) {
    vector<big> dp(105);
    dp[0] = dp[1] = 1;
    for(int i = 2; i <= 100; ++i){
        dp[i] = dp[i-1]+dp[i-2];
    }

    ll fib_bits = 0;

    {
        big x = dp[B+1];
        while(x){
            fib_bits++;
            x >>= 1;
        }
    }

    vector<ll> a(n);
    rep(i,n) a[i] = A[i]-'X';

    ll firstx = -1;
    vector<ll> b(n);

    rep(i,n){
        if(a[i] != 0){
            if(firstx == -1){
                b[i] = 0;
                conts;
            }
        }

        if(a[i] == 0){
            b[i] = 0;
            if(firstx == -1){
                firstx = i;
            }
        }
        else if(a[i] == 1){
            b[i] = 0;
        }
        else{
            b[i] = 1;
            if(b[i-1]){
                b[i-1] = 0;
            }
        }
    }

    if(firstx == -1){
        firstx = n;
    }

    rep(i,n-1){
        assert(!(b[i]&b[i+1]));
    }

    rep(bit,17){
        if(firstx&(1<<bit)){
            Send(1);
        }
        else{
            Send(0);
        }
    }

    rep(block,ceil2(n-1,B)){
        big ord = 0;
        ll ptr = B;
        for(int i = block*B; i < (block+1)*B; ++i){
            ll x = 0;
            if(i < n) x = b[i];
            if(x){
                ord += dp[ptr];
            }
            ptr--;
        }

        rep(bit,fib_bits){
            Send(ord&1);
            ord >>= 1;
        }
    }
}

#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(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-773760
edi

*/

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

typedef __int128 big;

void my_print2(big x){
    string s = "";
    while(x){
        s.pb(char('0'+x%10));
        x /= 10;
    }
    reverse(all(s));
    cout << s << endl;
}

#include "Bruno.h"

void Bruno(int n, int m, std::vector<int> A) {
    vector<big> dp(105);
    dp[0] = dp[1] = 1;
    for(int i = 2; i <= 100; ++i){
        dp[i] = dp[i-1]+dp[i-2];
    }

    ll fib_bits = 0;
    
    {
        big x = dp[B+1];
        while(x){
            fib_bits++;
            x >>= 1;
        }
    }

    auto get = [&](ll s, ll cnt){
        big val = 0;

        for(int i = s+cnt-1; i >= s; --i){
            val = (val<<1)|A[i];
        }

        return val;
    };

    ll firstx = get(0,17);
    ll read_ptr = 17;

    if(firstx == n){
        rep(i,n){
            Remove(i);
        }
        return;
    }

    rep(i,firstx){
        Remove(i);
    }

    vector<ll> a(n);

    rep(block,ceil2(n-1,B)){
        big val = get(read_ptr,fib_bits);

        read_ptr += fib_bits;
        ll ptr = B;

        for(int i = block*B; i < (block+1)*B and i < n; ++i){
            if(val >= dp[ptr]){
                a[i] = 1;
                val -= dp[ptr];
            }
            ptr--;
        }

        assert(val == 0);
    }

    vector<ll> curr;
    curr.pb(firstx);

    for(int i = firstx+1; i < n; ++i){
        curr.pb(i);

        if(a[i] == 1){
            curr.pop_back();
            while(sz(curr) > 1){
                Remove(curr.back());
                curr.pop_back();
            }
            Remove(i);
        }
    }

    while(!curr.empty()){
        Remove(curr.back());
        curr.pop_back();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 792 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 0 ms 792 KB Output is correct
4 Correct 1 ms 996 KB Output is correct
5 Correct 0 ms 792 KB Output is correct
6 Correct 0 ms 772 KB Output is correct
7 Correct 0 ms 792 KB Output is correct
8 Correct 0 ms 780 KB Output is correct
9 Correct 0 ms 780 KB Output is correct
10 Correct 1 ms 792 KB Output is correct
11 Correct 0 ms 792 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9756 KB Output is correct
2 Correct 39 ms 9748 KB Output is correct
3 Correct 38 ms 9844 KB Output is correct
4 Correct 37 ms 9864 KB Output is correct
5 Correct 38 ms 9888 KB Output is correct
6 Correct 39 ms 9800 KB Output is correct
7 Correct 38 ms 9876 KB Output is correct
8 Correct 39 ms 9888 KB Output is correct
9 Correct 39 ms 9620 KB Output is correct
10 Correct 38 ms 9876 KB Output is correct
11 Correct 38 ms 9888 KB Output is correct
12 Correct 38 ms 9648 KB Output is correct
13 Correct 45 ms 10632 KB Output is correct
14 Correct 45 ms 9744 KB Output is correct
15 Correct 44 ms 9880 KB Output is correct
16 Correct 49 ms 9780 KB Output is correct
17 Correct 46 ms 10556 KB Output is correct
18 Correct 44 ms 9300 KB Output is correct
19 Correct 42 ms 9224 KB Output is correct
20 Correct 37 ms 9704 KB Output is correct
21 Correct 37 ms 9864 KB Output is correct
22 Correct 48 ms 10652 KB Output is correct
23 Correct 38 ms 9888 KB Output is correct
24 Correct 37 ms 9804 KB Output is correct
25 Correct 43 ms 9192 KB Output is correct
26 Correct 45 ms 10568 KB Output is correct
27 Correct 44 ms 9652 KB Output is correct
28 Correct 44 ms 10556 KB Output is correct
29 Correct 43 ms 9184 KB Output is correct
30 Correct 42 ms 9872 KB Output is correct
31 Correct 42 ms 9324 KB Output is correct
32 Correct 38 ms 9804 KB Output is correct
33 Correct 38 ms 9704 KB Output is correct