oj.uz

Submission #426678

# Submission time Handle Problem Language Result Execution time Memory
426678 2021-06-14T08:56:51 Z 반딧불(#7615) Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 68 ms 7980 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 70
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;
    LIM = 100000 / 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 = 1;
            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);
        }
    }
//    Send(strange);
}

#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 70
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;
    LIM = 100000 / 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];
            }
        }
    }

//    if(A.back()){
//        for(int i=0; i<n; i++){
//            if(arr[i]){
//                arr[i+1] = 1;
//                break;
//            }
//        }
//    }


    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:80:13: warning: unused variable 'cnt' [-Wunused-variable]
   80 |         int cnt = accumulate(arr+L, arr+R, 0);
      |             ^~~
Anna.cpp:55:9: warning: variable 'strange' set but not used [-Wunused-but-set-variable]
   55 |     int strange = 0;
      |         ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1892 KB Output is correct
2 Correct 25 ms 1892 KB Output is correct
3 Correct 20 ms 2036 KB Output is correct
4 Correct 20 ms 1912 KB Output is correct
5 Correct 20 ms 1984 KB Output is correct
6 Correct 19 ms 1904 KB Output is correct
7 Correct 20 ms 1864 KB Output is correct
8 Correct 20 ms 1876 KB Output is correct
9 Correct 23 ms 1952 KB Output is correct
10 Correct 20 ms 2068 KB Output is correct
11 Correct 19 ms 1896 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7936 KB Output is correct
2 Correct 66 ms 7960 KB Output is correct
3 Incorrect 67 ms 7980 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -