oj.uz

Submission #475408

# Submission time Handle Problem Language Result Execution time Memory
475408 2021-09-22T09:36:05 Z balbit Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 2000 ms 1780 KB 
#include "Anna.h"
#include <bits/stdc++.h>
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 ;

const int maxbit = 7e4;
const int len = maxbit / 60;
const ll cap = (1ull<<60)-1;

ll a0[len], a1[len], a2[len];
ll sig[len];

void add(ll *A, ll *B, ll *C) {
    memset(C, 0, sizeof *C);
    for (int i = 0; i<len-1; ++i) {
        C[i] = A[i] + B[i];
        C[i+1] |= C[i] >> 60;
        C[i] &= cap;
    }
}

void addto(ll *A, ll *B) {
    // add a to b
    for (int i = 0; i<len-1; ++i) {
        B[i] += A[i];
        B[i+1] |= B[i] >> 60;
        B[i] &= cap;
    }
}

vector<int> spit(ll *A){
    vector<int> ret;
    for (int i = 0; i<len-1; ++i) {
        REP(j,60) {
            ret.pb((A[i]>>j)&1);
        }
    }
    while (!ret.empty() && ret.back() == 0) ret.pop_back();
    return ret;
}


}

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


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);
    }

    ll *f0 = a0;
    f0[0] = 1;
    ll *f1 = a1;
    f1[0] = 2;
    ll *tmp = a2;
    ll *sum = sig;

    REP(i, n) {
        // position 0: 1, position 1: 2, position 2: 3, position 3: 5, etc
//        bug(i, f0.a[0], f1.a[0]);
//        bug(ret[i]);
        if (ret[i] == 1) {
            addto(f1, sum);
            bug(i, f1[0]);
        }
        add(f0, f1, tmp);
        swap(f0, f1);
        swap(f1, tmp);
    }

    bug(sum[0]);

    vector<int> tosend = spit(sum);

//    for (int x : fib) cout<<x<<' ';
//    cout<<endl;

    REP(i,SZ(tosend)) {
        bug( i);
        Send(tosend[i]);
    }
}



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

#include "Bruno.h"
#include <bits/stdc++.h>
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 = 1e5+5;

const int maxbit = 7e4;
const int len = maxbit / 60;
const ll cap = (1ll<<60)-1;

ll a0[len], a1[len], a2[len];
ll coco[len];

void add(ll *A, ll *B, ll *C) {
    memset(C, 0, sizeof *C);
    for (int i = 0; i<len-1; ++i) {
        C[i] = A[i] + B[i];
        C[i+1] |= C[i] >> 60;
        C[i] &= cap;
    }
}

void sub(ll *A, ll *B, ll *C) {
    // C = A-B
    memset(C, 0, sizeof *C);
    for (int i = 0; i<len-1; ++i) {
        C[i] += A[i] - B[i];
        if (C[i] < 0) {
            C[i] += (1ll<<60);
            C[i+1] --;
        }
    }
}

void addto(ll *A, ll *B) {
    // add a to b
    for (int i = 0; i<len-1; ++i) {
        B[i] += A[i];
        B[i+1] |= B[i] >> 60;
        B[i] &= cap;
    }
}

void subfrom(ll *A, ll *B) {
    // subtract a from b
    for (int i = 0; i<len-1; ++i) {
        B[i] -= A[i];
        if (B[i] < 0) {
            B[i] += 1ll<<60;
            B[i+1]--;
        }
    }
}

bool geq(ll *A, ll *B) {
    // is A >= B?
    RREP(i,len) {
        if (A[i] > B[i]) return 1;
        if (A[i] < B[i]) return 0;
    }
    return 1;
}

void eat(ll *A, vector<int> v) {
    REP(i, SZ(v)) {
        if (v[i])
            A[i/60] |= (1ll << (i%60));
    }
}

int far[maxn];

}  // 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 ;
    }
    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]);
    }

    ll * code = coco;
    eat(code, rest);

    ll * f0 = a0;
    ll * f1 = a1;
    ll * tmp = a2;
    f1[0] = 1;

    int at = 0; // considering position

    while (geq(code, f1)) {
        add(f0,f1,tmp);
        swap(f0, f1);
        swap(f1, tmp);
        ++at;
    }

    while (at >= 3) {
        if (geq(code,f0)) {
            subfrom(f0, code);
            far[at-3] = 1;
            bug("Took ", at);
        }
        sub(f1,f0,tmp);
        swap(f1,f0);
        swap(f0,tmp);
        --at;
    }

    bug(code[0]);

    vector<int> Yay;
    int tit = 0;
    while (SZ(Yay) < n) {
        if (far[tit]) {
            Yay.pb(1);
        }
        else Yay.pb(0);
        bug(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);
}

Compilation message

Bruno.cpp:69:6: warning: 'void {anonymous}::addto(long long int*, long long int*)' defined but not used [-Wunused-function]
   69 | void addto(ll *A, ll *B) {
      |      ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1388 KB Output is correct
2 Correct 1 ms 1384 KB Output is correct
3 Correct 1 ms 1388 KB Output is correct
4 Correct 2 ms 1272 KB Output is correct
5 Correct 2 ms 1388 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 1 ms 1388 KB Output is correct
8 Correct 2 ms 1256 KB Output is correct
9 Correct 1 ms 1264 KB Output is correct
10 Correct 1 ms 1260 KB Output is correct
11 Correct 1 ms 1264 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1780 KB Time limit exceeded
2 Halted 0 ms 0 KB -