Submission #935774

#	Time	Username	Problem	Language	Result	Execution time	Memory
935774		quanlt206	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	51 ms	9488 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
 
template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */
 
const int N = 1e5 + 7;
const int BLOCK = 64;
const int bit_size = 44;
 
int n, m;
 
vector<int> bit, val_remove;
 
ll f[N];
 
vector<int> old_data, new_data;
 
vector<char> glS;
int res = 0;
 
void convert_to_longlong(vector<int> B) {
    ll idx = 0;
    f[0] = 1;
    f[1] = 1;
    FOR(i, 2, BLOCK) f[i] = f[i - 1] + f[i - 2];
    REP(i, 0, (int)B.size())
        if (B[i] == 1) {
            idx+=f[(int)B.size() - i];
        }
    FORD(i, bit_size, 0) Send((idx >> i) & 1);
}
 
void Convert(vector<int> A) {
    while ((int)A.size() % BLOCK != 0) A.push_back(0);
    for (int i = 0; i < (int)A.size(); i+=BLOCK) {
        vector<int> B;
        FOR(j, i, i + BLOCK - 1) B.push_back(A[j]);
        convert_to_longlong(B);
    }
}
 
void Anna(int n, vector<char> S) {
    bool kt = false;
    int i = 0;
    bool find_XZ = false, find_X = false;
    while (i < n) {
        if (S[i] != 'Z') {
            i++;
            continue;
        }
        int j = i;
        while (j + 1 < n && S[j + 1] == S[j]) j++;
        FOR(k, i, j - 1) S[k] = 'Y';
        i = j + 1;
    }
    REP(i, 0, n)
        if (S[i] == 'X') {
            find_X = true;
            if (i + 1 < n && S[i + 1] == 'Z') find_XZ = true;
            break;
        }
    vector<int> A;
    bool ok = false;
    for (auto x : S)
        if (!ok) {
            if (x == 'Y' || x == 'Z') A.push_back(0); else {
                ok = true;
                A.push_back(1);
            }
        }
        else {
            if (x == 'Z') A.push_back(1); else A.push_back(0);
        }
    if (!find_X) {
        A.clear();
        REP(i, 0, n) A.push_back(0);
    }
    old_data = A;
//    cout<<"old data :\n";
//    for (auto x : old_data) cout<<x<<" "; cout<<"\n";
    if (find_XZ) {
        REP(i, 0, (int)A.size())
            if (S[i] == 'X') {
                A[i + 1] = 0;
                break;
            }
    }
    A.push_back(0);
    A.push_back(find_XZ);
 
//    for (auto x : A) cout<<x<<" "; cout<<"\n";
    Convert(A);
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
 
template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */
 
const int N = 1e5 + 7;
const int BLOCK = 64;
const int bit_size = 44;
 
int n, m;
 
vector<int> bit, val_remove;
 
ll f[N];
 
vector<int> old_data, new_data;
 
vector<char> glS;
int res = 0;
 
vector<int> convert_to_array(ll idx) {
    f[0] = 1;
    f[1] = 1;
    FOR(i, 2, BLOCK) f[i] = f[i - 1] + f[i - 2];
//    cerr<<idx<<endl;
    vector<int> res;
    idx++;
    int i = 0;
    REP(i, 0, BLOCK) {
        if (idx > f[BLOCK - i]) {
            res.push_back(1);
            idx-=f[BLOCK - i];
        }
        else {
            res.push_back(0);
        }
    }
    return res;
}
 
vector<int> convert_to_array(int L, vector<int> A) {
    vector<int> res;
//    for (auto x : A) cerr<<x<<" "; cerr<<endl;
    for (int i = 0; i < L; i+=bit_size + 1) {
        ll tmp = 0;
        FOR(j, i, i + bit_size) tmp = tmp * 2 + A[j];
//        exit(0);
        vector<int> arr = convert_to_array(tmp);
        for (auto x : arr) res.push_back(x);
    }
    return res;
}
 
void Bruno(int n, int L, vector<int> A) {
    A = convert_to_array(L, A);
//    for (auto x : A) cout<<x<<" "; cout<<"\n";
    while ((int)A.size() > n + 2) A.pop_back();
    int find_XZ = A.back();
    A.pop_back();
    A.pop_back();
    new_data = A;
    if (*mxx(all(A)) == 0) {
        REP(i, 0, n) Remove(i);
        return ;
    }
    int pos = 0;
    REP(i, 0, n)
        if (A[i] == 1) {
            pos = i;
            break;
        }
    if (find_XZ) A[pos + 1] = 1;
    new_data = A;
//    cout<<"new data : \n";
//    for (auto x : A) cout<<x<<" "; cout<<"\n";
    REP(i, 0, pos) Remove(i);
    if (pos == n - 1) {
        Remove(pos);
        return ;
    }
    int i = pos;
    while (i < n) {
        if (i == n - 1) break;
        int j = i + 1;
        while (j < n && A[j] == 0) j++;
        if (j >= n) {
            REP(k, i + 1, n) Remove(k);
            i = n - 1;
            break;
        }
        FORD(k, j - 1, i + 1) Remove(k);
        if (j > pos) Remove(j);
        i = j;
    }
    if (pos != i) Remove(pos);
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:80:10: warning: unused variable 'kt' [-Wunused-variable]
   80 |     bool kt = false;
      |          ^~

Bruno.cpp: In function 'std::vector<int> convert_to_array(ll)':
Bruno.cpp:65:9: warning: unused variable 'i' [-Wunused-variable]
   65 |     int i = 0;
      |         ^

• Subtask 1: 5 / 5
• Subtask 2: 94 / 95