oj.uz

Submission #426653

# Submission time Handle Problem Language Result Execution time Memory
426653 2021-06-14T08:44:35 Z 반딧불(#7615) Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 65 ms 7844 KB 
#include "Anna.h"
#include <bits/stdc++.h>

#ifdef TEST
#define LIM_A 50
#define LIM_B 35
typedef long long ll;
#else
#define LIM_A 100
#define LIM_B 69
typedef __int128 ll;
#endif // TEST

using namespace std;

namespace {
    int n;
    bool arr[100002];
    ll DP[502][2];
    ll power[102];
}

void doSmall(vector<char> &S){
    int xOpen = -1;
    for(int i=0; i<n; i++){
        if(xOpen == -1){
            if(S[i] != 'X') Send(0);
            else{
                Send(1);
                xOpen = i;
            }
            continue;
        }

        if(S[i] == 'Z' && S[i+1] != 'Z') Send(1);
        else Send(0);
    }
}

void Anna(int N, vector<char> S) {
    int LIM = (N + LIM_A - 1) / LIM_A;
    n = N;
//    if(n<=70000){
//        doSmall(S);
//        return;
//    }

    power[0] = 1;
    for(int i=1; i<=LIM_A; i++){
        power[i] = power[i-1] * 2;
    }

    int xOpen = -1;
    int strange = 0;
    for(int i=0; i<n; i++){
        if(xOpen == -1){
            if(S[i] != 'X'){}
            else{
                arr[i] = 1;
                xOpen = i;
            }
            continue;
        }

        if(S[i] == 'Z' && S[i+1] != 'Z'){
            if(arr[i-1] == 1) strange = i;
            else arr[i] = 1;
        }
    }

    DP[0][0] = 1;
    for(int i=1; i<=LIM_A; i++){
        DP[i][0] = DP[i-1][0] + DP[i-1][1];
        DP[i][1] = DP[i-1][0];
    }

    for(int d=0; d<LIM; d++){
        int L = d*LIM_A, R = L+LIM_A;
        int cnt = accumulate(arr+L, arr+R, 0);
        ll sum = 0;

        for(int i=LIM_A, x=L; x<R; x++, i--){
            if(arr[x]){
                sum += DP[i][0];
            }
        }
        for(int i=0; i<LIM_B; i++){
            ll tmp = sum;
            for(int a=0; a<i; a++) tmp /= ll(2);
            Send(tmp%2);
        }
    }

    for(int d=0; d<20; d++) Send((strange>>d)&1);
}

#include "Bruno.h"
#include <bits/stdc++.h>

#ifdef TEST
#define LIM_A 50
#define LIM_B 35
typedef long long ll;
#else
#define LIM_A 100
#define LIM_B 69
typedef __int128 ll;
#endif // TEST

using namespace std;

namespace {
    int n;
    int arr[100002];
    ll DP[502][2];
    ll power[102];
    vector<int> X, Z;
}  // namespace

void Bruno(int N, int L, vector<int> A) {
    n = N;
    int LIM = (N + LIM_A - 1) / LIM_A;
//    if(n<=70000){
//        for(int i=0; i<n; i++){
//            arr[i] = A[i];
//        }
//    }
    DP[0][0] = 1;
    for(int i=1; i<=LIM_A; i++){
        DP[i][0] = DP[i-1][0] + DP[i-1][1];
        DP[i][1] = DP[i-1][0];
    }

    power[0] = 1;
    for(int i=1; i<=LIM_A; i++){
        power[i] = power[i-1] * 2;
    }

    for(int d=0; d<LIM; d++){
        int L = d*LIM_A, R = d*LIM_A+LIM_A;
        ll sum = 0;
        for(int x=0; x<LIM_B; x++){
            if(A[d*LIM_B+x]) sum += power[x];
        }
        for(int i=LIM_A, x=L; x<R; i--, x++){
            if(sum >= DP[i][0]){
                arr[x] = 1;
                sum -= DP[i][0];
            }
        }
    }

    ll tmp = 0;
    for(ll x=0; x<20; x++){
        if(A[LIM*LIM_B+x]) tmp += (1<<x);
    }
    if(tmp) arr[tmp] = 1;


    int f = -1;
    for(int i=0; i<n; i++){
        if(f == -1){
            if(!arr[i]) Remove(i);
            else f=i;
            continue;
        }
        if(arr[i]){
            Remove(i);
            continue;
        }
        int j = i;
        while(j+1<n && !arr[j+1]) j++;
        for(int k=j; k>=i; k--) Remove(k);
        i=j;
    }

    if(f != -1) Remove(f);
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:79:13: warning: unused variable 'cnt' [-Wunused-variable]
   79 |         int cnt = accumulate(arr+L, arr+R, 0);
      |             ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 2 ms 484 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 7844 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -