oj.uz

Submission #996680

# Submission time Handle Problem Language Result Execution time Memory
996680 2024-06-11T05:09:12 Z hotboy2703 Ancient Machine (JOI21_ancient_machine) C++17
97 / 100
 44 ms 10652 KB 
#include "Anna.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

namespace A{
    const ll BIG = 14;
    const ll SMALL = 10;
    struct pt{
        ll type,l,r;
    };
    vector <ll> all;
    void init(){
        for (ll i = 0;i < MASK(BIG);i ++){
            bool ok = 1;
            for (ll j = 1;j < BIG;j ++){
                if (BIT(i,j)&&BIT(i,j-1))ok = 0;
            }
            if (ok)all.push_back(i);
        }
    }
}

void Anna(int N, std::vector<char> S) {
    using namespace A;
    vector <ll> a;
    for (ll i = 0;i < N;i ++){
        a.push_back(S[i]-'X');
    }
//    for (auto x:a)cout<<x<<' ';
//    cout<<'\n';
    vector <ll> res(N+BIG);
    vector <pt> nw;
    for (ll i = 0;i < N;i ++){
        ll j = i;
        while (j + 1 < N && a[j+1] == a[i])j++;
        nw.push_back({a[i],i,j});
        i = j;
    }
    while (!nw.empty() && nw.back().type != 2){
        nw.pop_back();
    }
    ll last0 = -1;
    for (ll i = 0;i < sz(nw);i ++){
        if (last0 == -1){
            if (nw[i].type == 0){res[nw[i].r] = 1;last0 = nw[i].r;}
        }
        else{
            ll j = i;
            while (nw[j].type != 2)j++;
            bool ok = 0;
            for (ll k = j-1;k >= i;k --){
                if (nw[k].type==1)ok = 1;
            }
            res[nw[j].r] = 1;
            i = j;
        }
    }
//    for (auto x:res)cout<<x<<' ';
//    cout<<'\n';
//for (ll i = 0;i < N;i ++)cout<<res[i]<<' ';
//    cout<<'\n';
    init();
    vector <ll> res2;
    if (last0 != -1){
        for (ll j = 0;j < 20;j ++)res2.push_back(BIT(last0,j));
        for (ll j = last0 + 1;j < N;j += BIG){
            ll mask = 0;
            for (ll k = 0;k < BIG;k ++){
                mask += MASK(k) * res[j+k];
            }
            mask = lower_bound(all.begin(),all.end(),mask) - all.begin();
            for (ll k = 0;k < SMALL;k ++){
                res2.push_back(BIT(mask,k));
            }
        }
    }
    else{
    }
    for (auto x:res2)Send(x);
}

#include "Bruno.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

namespace B{
    const ll BIG = 14;
    const ll SMALL = 10;
    vector <ll> all;
    void init(){
        for (ll i = 0;i < MASK(BIG);i ++){
            bool ok = 1;
            for (ll j = 1;j < BIG;j ++){
                if (BIT(i,j)&&BIT(i,j-1))ok = 0;
            }
            if (ok)all.push_back(i);
        }
    }
}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
    using namespace B;
    init();
    vector <ll> a(N+BIG);
    if (!A.empty()){
        ll last0 = 0;
        for (ll i = 0;i < 20;i ++)last0 += MASK(i) * A[i];
//        cout<<last0<<'\n';
        a[last0] = 1;
        for (ll i = 20,ptr_a = last0 + 1;i < sz(A);i += SMALL,ptr_a += BIG){
            ll mask = 0;
            for (ll j = 0;j < SMALL;j ++)mask += MASK(j) * A[i+j];
            mask = all[mask];
            for (ll j = 0;j < BIG;j ++)a[ptr_a+j] = BIT(mask,j);
        }
    }
//    for (ll i = 0;i < N;i ++)cout<<a[i]<<' ';
//    cout<<'\n';
    vector <bool> del(N);
    ll last = -1;
    ll first = -1;
    for (ll i = 0;i < N;i ++){
        if (a[i]){
            if (first==-1)first = a[i];
            else{
                for (ll j = i - 1;j > last;j --){del[j] = 1;Remove(j);}
                del[i] = 1;Remove(i);
            }
            last = i;
        }
    }
    for (ll i = 0;i < N;i ++){
        if (!del[i]){
            Remove(i);
        }
    }
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:59:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   59 |             bool ok = 0;
      |                  ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 776 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 2 ms 784 KB Output is correct
4 Correct 0 ms 796 KB Output is correct
5 Correct 1 ms 796 KB Output is correct
6 Correct 1 ms 796 KB Output is correct
7 Correct 1 ms 788 KB Output is correct
8 Correct 2 ms 796 KB Output is correct
9 Correct 1 ms 796 KB Output is correct
10 Correct 1 ms 780 KB Output is correct
11 Correct 0 ms 792 KB Output is correct

Subtask #2
92.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 36 ms 10300 KB Partially correct
2 Partially correct 34 ms 10240 KB Partially correct
3 Partially correct 37 ms 10500 KB Partially correct
4 Partially correct 34 ms 10192 KB Partially correct
5 Partially correct 33 ms 10168 KB Partially correct
6 Partially correct 33 ms 10196 KB Partially correct
7 Partially correct 38 ms 10200 KB Partially correct
8 Partially correct 34 ms 10192 KB Partially correct
9 Partially correct 35 ms 10120 KB Partially correct
10 Partially correct 35 ms 10148 KB Partially correct
11 Partially correct 34 ms 10328 KB Partially correct
12 Partially correct 34 ms 10208 KB Partially correct
13 Partially correct 42 ms 10392 KB Partially correct
14 Partially correct 44 ms 10352 KB Partially correct
15 Partially correct 36 ms 10652 KB Partially correct
16 Partially correct 34 ms 10432 KB Partially correct
17 Correct 34 ms 8080 KB Output is correct
18 Correct 32 ms 7732 KB Output is correct
19 Correct 39 ms 7816 KB Output is correct
20 Partially correct 35 ms 10452 KB Partially correct
21 Partially correct 34 ms 10416 KB Partially correct
22 Partially correct 41 ms 9564 KB Partially correct
23 Partially correct 35 ms 10372 KB Partially correct
24 Partially correct 33 ms 10444 KB Partially correct
25 Correct 33 ms 8008 KB Output is correct
26 Correct 33 ms 8028 KB Output is correct
27 Correct 33 ms 7924 KB Output is correct
28 Correct 34 ms 7948 KB Output is correct
29 Correct 34 ms 7664 KB Output is correct
30 Correct 38 ms 7928 KB Output is correct
31 Correct 32 ms 8124 KB Output is correct
32 Partially correct 34 ms 10252 KB Partially correct
33 Partially correct 36 ms 10200 KB Partially correct