oj.uz

Submission #426673

# Submission time Handle Problem Language Result Execution time Memory
426673 2021-06-14T08:55:04 Z 반딧불(#7615) Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 77 ms 8084 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);
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1896 KB Output is correct
2 Correct 20 ms 1952 KB Output is correct
3 Correct 20 ms 1908 KB Output is correct
4 Correct 22 ms 1996 KB Output is correct
5 Correct 20 ms 2008 KB Output is correct
6 Correct 20 ms 1936 KB Output is correct
7 Correct 19 ms 1892 KB Output is correct
8 Correct 20 ms 1888 KB Output is correct
9 Correct 20 ms 1892 KB Output is correct
10 Correct 24 ms 1904 KB Output is correct
11 Correct 20 ms 1896 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 72 ms 7928 KB Partially correct
2 Partially correct 64 ms 7928 KB Partially correct
3 Partially correct 71 ms 8084 KB Partially correct
4 Partially correct 67 ms 7956 KB Partially correct
5 Partially correct 66 ms 8012 KB Partially correct
6 Partially correct 66 ms 7920 KB Partially correct
7 Partially correct 65 ms 7940 KB Partially correct
8 Partially correct 68 ms 7924 KB Partially correct
9 Partially correct 65 ms 7944 KB Partially correct
10 Partially correct 68 ms 7920 KB Partially correct
11 Partially correct 77 ms 7940 KB Partially correct
12 Incorrect 64 ms 7928 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -