oj.uz

Submission #475436

# Submission time Handle Problem Language Result Execution time Memory
475436 2021-09-22T11:16:36 Z balbit Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 79 ms 9088 KB 
#include "Anna.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif






namespace {

const int maxn = 1e5+5;
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


}

//#ifdef BALBIT
//void Send(int x) {
//    bug("Sent: ", x);
//}
//#endif // BALBIT

ull fib[100];


void Anna(int n, std::vector<char> S) {

    vector<int> ret(n);
    bool zed = 0;
    int wherezed = n;
    for (int i = n-1; i>=0; --i) {
        if (S[i] == 'Z' && !zed) {
            zed = 1;
            wherezed = i;
        }
        else if (S[i] == 'X' && zed && (i==0 || S[i-1] != 'X')) {
            ret[i] = 1;
        }
    }

    // Send wherezed
    REP(i, 17) {
        Send((wherezed>>i)&1);
    }

    fib[0] = 1; fib[1] = 1;

    for (int i = 2; i<=63; ++i) {
        fib[i] = fib[i-1] + fib[i-2];
//        bug(i, ULLONG_MAX,fib[i]);
    }
    bug(__lg(fib[63]));

//    bug(__lg(fib[64]));



    for (int i = 0; i<n; i+=63) {

        ll tmp = 0;
        REP(j,63) {
            if ((i+j) < n && ret[i+j]) tmp += fib[j+1];
        }
        REP(j, 44) {
            Send((tmp >> j) & 1);
        }
    }

}



//int main(){
//    Anna(6, {'Z','X','Y','X','Z','Z'});
//}

#include "Bruno.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")

using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif



namespace {

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;

const int maxn = 2e5+5;

int far[maxn];
ll fib[100];

}  // namespace



void Bruno(int n, int L, std::vector<int> A) {

//    if (*max_element(ALL(A)) == 0) {
//    }

    int zpos = 0;
    REP(i,17){
        zpos += A[i] << i ;
    }

    fib[0] = fib[1] = 1;
    for (int i = 2; i<=63; ++i) fib[i] = fib[i-1] + fib[i-2];
    if (zpos == n) {
        REP(i,n) {
            Remove(i);
        }
        return;
    }
    bug(zpos);
    vector<int> rest;
    for (int i = 17; i<SZ(A); ++i) {
        rest.pb(A[i]);
    }

    for (int i = 0; i<SZ(rest); i+=44) {
        ll tt = 0;
        REP(j,44) {
            if ((i+j<SZ(rest)) && rest[i+j]) tt += 1ll<<j;
        }
        bug(i,tt);
        for (int j = 63; j>=1; --j) {
            if (tt >= fib[j]) {
                tt -= fib[j];
                if (i != 0)
                bug(i,j);
                far[(i/44)*63+j-1] = 1;
            }

        }

    }


    vector<int> Yay;
    int tit = 0;
    while (SZ(Yay) < n) {
        if (far[tit]) {
            Yay.pb(1);
        }
        else Yay.pb(0);
        bug(tit, Yay.back());
        ++tit;
    }

    Yay[zpos] = 1;
    bug(zpos);


    for (int i = n-1; i>=0; --i) {
        if (Yay[i] == 1) {
            zpos = i;
            break;
        }else{
            Remove(i);
        }
    }



    int prv = zpos;
    for (int i = zpos-1; i>=0; --i) {
        if (Yay[i] == 1 || i == 0) {
            // met an x
            for (int j = i+1; j<prv; ++j) {
                Remove(j);
            }
            Remove(i);
            prv = i;
        }
    }
    Remove(zpos);



}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 484 KB Output is correct
2 Correct 0 ms 480 KB Output is correct
3 Correct 0 ms 492 KB Output is correct
4 Correct 0 ms 484 KB Output is correct
5 Correct 0 ms 484 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 0 ms 484 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 0 ms 484 KB Output is correct
11 Correct 0 ms 484 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8576 KB Output is correct
2 Correct 62 ms 9008 KB Output is correct
3 Correct 62 ms 8940 KB Output is correct
4 Correct 65 ms 8964 KB Output is correct
5 Correct 65 ms 8944 KB Output is correct
6 Correct 57 ms 8996 KB Output is correct
7 Correct 60 ms 8900 KB Output is correct
8 Correct 59 ms 8936 KB Output is correct
9 Correct 62 ms 8936 KB Output is correct
10 Correct 60 ms 9032 KB Output is correct
11 Correct 57 ms 9048 KB Output is correct
12 Correct 72 ms 8980 KB Output is correct
13 Correct 69 ms 8940 KB Output is correct
14 Correct 64 ms 8480 KB Output is correct
15 Correct 65 ms 9088 KB Output is correct
16 Correct 65 ms 8896 KB Output is correct
17 Correct 68 ms 8284 KB Output is correct
18 Correct 67 ms 8260 KB Output is correct
19 Correct 76 ms 8528 KB Output is correct
20 Correct 79 ms 8904 KB Output is correct
21 Correct 58 ms 8956 KB Output is correct
22 Correct 68 ms 8548 KB Output is correct
23 Correct 72 ms 9028 KB Output is correct
24 Correct 59 ms 8844 KB Output is correct
25 Correct 64 ms 8612 KB Output is correct
26 Correct 67 ms 8292 KB Output is correct
27 Correct 65 ms 8652 KB Output is correct
28 Correct 64 ms 8292 KB Output is correct
29 Correct 65 ms 8576 KB Output is correct
30 Correct 69 ms 8260 KB Output is correct
31 Correct 65 ms 8640 KB Output is correct
32 Correct 57 ms 8944 KB Output is correct
33 Correct 61 ms 8884 KB Output is correct