#765336 (C++17) No.1951 消えたAGCT(2)

提出ソース

結果

問題	No.1951 消えたAGCT(2)
ユーザー	raven7959
提出日時	2022-05-23 10:04:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	378 ms / 3,000 ms
コード長	10,663 bytes
コンパイル時間	2,709 ms
コンパイル使用メモリ	204,228 KB
実行使用メモリ	50,688 KB
最終ジャッジ日時	2023-10-20 17:26:49
合計ジャッジ時間	8,272 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	1 ms 4,348 KB
testcase_07	AC	1 ms 4,348 KB
testcase_08	AC	150 ms 50,688 KB
testcase_09	AC	151 ms 50,688 KB
testcase_10	AC	149 ms 50,688 KB
testcase_11	AC	148 ms 50,688 KB
testcase_12	AC	91 ms 31,788 KB
testcase_13	AC	11 ms 5,016 KB
testcase_14	AC	352 ms 47,524 KB
testcase_15	AC	273 ms 39,072 KB
testcase_16	AC	296 ms 41,184 KB
testcase_17	AC	378 ms 50,688 KB
testcase_18	AC	361 ms 50,688 KB
testcase_19	AC	361 ms 50,688 KB
testcase_20	AC	368 ms 50,688 KB
testcase_21	AC	145 ms 50,688 KB
testcase_22	AC	145 ms 50,688 KB
testcase_23	AC	151 ms 50,688 KB
testcase_24	AC	145 ms 50,688 KB
testcase_25	AC	150 ms 50,688 KB
testcase_26	AC	366 ms 50,688 KB
testcase_27	AC	370 ms 50,688 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n"
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vld = vector<long double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvs = vector<vector<string>>;
using vvc = vector<vector<char>>;
using vvd = vector<vector<double>>;
using vvld = vector<vector<long double>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int INF = 1e9;
const ll LINF = 2e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
bool ispow2(int i) { return i && (i & -i) == i; }
bool ispow2(ll i) { return i && (i & -i) == i; }
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

static uint32_t RandXor(){
    static uint32_t x=123456789;
    static uint32_t y=362436069;
    static uint32_t z=521288629;
    static uint32_t w=88675123;
    uint32_t t;
 
    t=x^(x<<11);
    x=y; y=z; z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}

static double Rand01(){
    return (RandXor()+0.5)*(1.0/UINT_MAX);
}

// BinaryTrie<int,30> BT; などする
// void add(INT val): BTに入っている数字全てにvalをXORする
// INT get(Node *v): ポインタvに対応した値を返す(BTに入っている値,XORした時のk番目とかのときはあとで自分でXORする)
// Node* find(INT val): valに対応したポインタを返す
// void insert(INT val,size_t k=1): valをk個追加する
// bool erase(INT val): valを1個削除する
// bool erase(Node *v,size_t k=1): ポインタvに対応した値をk個削除する
// Node* get_max(INT val=0): valをXORした時の最大の要素と対応したポインタを返す(復元はget(*ptr)^valする)
// Node* get_min(INT val=0): 上の最小バージョン
// Node* lower_bound(INT val): val以上で最小の要素に対応するポインタを返す
// Node* upper_bound(INT val): valより大で最小の要素に対応するポインタを返す
// size_t order_of_val(INT val): valが小さい方から何番目か返す(val未満の数の個数+1を返すとも)
// Node* get_kth(size_t k,INT val=0): valをXORした時の小さい方からk番目(0-indexed)の要素に対応したポインタを返す(復元はget(*ptr)^valする)

template <typename INT, size_t MAX_DIGIT>
struct BinaryTrie{
    struct Node{
        size_t count;
        Node *prev, *left, *right;
        Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}
    };
    INT lazy;
    Node *root;

    // constructor
    BinaryTrie() : lazy(0), root(emplace(nullptr)) {}
    inline size_t get_count(Node *v) const { return v ? v->count : 0; }

    // add and get value of Node
    inline void add(INT val){
        lazy ^= val;
    }
    inline INT get(Node *v){
        if (!v)
            return -1;
        INT res = 0;
        for (int i = 0; i < MAX_DIGIT; ++i){
            if (v == v->prev->right)
                res |= INT(1) << i;
            v = v->prev;
        }
        return res ^ lazy;
    }

    // find Node* whose value is val
    Node *find(INT val){
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            bool flag = (nval >> i) & 1;
            if (flag)
                v = v->right;
            else
                v = v->left;
            if (!v)
                return v;
        }
        return v;
    }

    // insert
    inline Node *emplace(Node *prev){
        return new Node(prev);
    }
    void insert(INT val, size_t k = 1){
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            bool flag = (nval >> i) & 1;
            if (flag && !v->right)
                v->right = emplace(v);
            if (!flag && !v->left)
                v->left = emplace(v);
            if (flag)
                v = v->right;
            else
                v = v->left;
        }
        v->count += k;
        while ((v = v->prev))
            v->count = get_count(v->left) + get_count(v->right);
    }

    // erase
    Node *clear(Node *v){
        if (!v || get_count(v))
            return v;
        delete (v);
        return nullptr;
    }
    bool erase(Node *v, size_t k = 1){
        if (!v)
            return false;
        v->count -= k;
        while ((v = v->prev)){
            v->left = clear(v->left);
            v->right = clear(v->right);
            v->count = get_count(v->left) + get_count(v->right);
        }
        return true;
    }
    bool erase(INT val){
        auto v = find(val);
        return erase(v);
    }

    // max (with xor-addition of val) and min (with xor-addition of val)
    Node *get_max(INT val = 0){
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            bool flag = (nval >> i) & 1;
            if (!v->right)
                v = v->left;
            else if (!v->left)
                v = v->right;
            else if (flag)
                v = v->left;
            else
                v = v->right;
        }
        return v;
    }
    Node *get_min(INT val = 0){
        return get_max(~val & ((INT(1) << MAX_DIGIT) - 1));
    }

    // lower_bound, upper_bound
    Node *get_cur_node(Node *v, int i){
        if (!v)
            return v;
        Node *left = v->left, *right = v->right;
        if ((lazy >> i) & 1)
            swap(left, right);
        if (left)
            return get_cur_node(left, i + 1);
        else if (right)
            return get_cur_node(right, i + 1);
        return v;
    }
    Node *get_next_node(Node *v, int i){
        if (!v->prev)
            return nullptr;
        Node *left = v->prev->left, *right = v->prev->right;
        if ((lazy >> (i + 1)) & 1)
            swap(left, right);
        if (v == left && right)
            return get_cur_node(right, i);
        else
            return get_next_node(v->prev, i + 1);
    }
    Node *lower_bound(INT val){
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            bool flag = (nval >> i) & 1;
            if (flag && v->right)
                v = v->right;
            else if (!flag && v->left)
                v = v->left;
            else if ((val >> i) & 1)
                return get_next_node(v, i);
            else
                return get_cur_node(v, i);
        }
        return v;
    }
    Node *upper_bound(INT val){
        return lower_bound(val + 1);
    }
    size_t order_of_val(INT val){
        Node *v = root;
        size_t res = 0;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            Node *left = v->left, *right = v->right;
            if ((lazy >> i) & 1)
                swap(left, right);
            bool flag = (val >> i) & 1;
            if (flag){
                res += get_count(left);
                v = right;
            }
            else
                v = left;
        }
        return res;
    }

    // k-th, k is 0-indexed
    Node *get_kth(size_t k, INT val = 0){
        Node *v = root;
        INT nval = val ^ lazy;
        if (get_count(v) <= k)
            return nullptr;
        for (int i = MAX_DIGIT - 1; i >= 0; --i){
            bool flag = (nval >> i) & 1;
            Node *left = (flag ? v->right : v->left);
            Node *right = (flag ? v->left : v->right);
            if (get_count(left) <= k)
                k -= get_count(left), v = right;
            else
                v = left;
        }
        return v;
    }

    // debug
    void print(Node *v, string prefix = ""){
        if (!v)
            return;
        cout << prefix << ": " << v->count << endl;
        print(v->left, prefix + "0");
        print(v->right, prefix + "1");
    }
    void print(){
        print(root);
    }
    vector<INT> eval(Node *v, int digit) const{
        vector<INT> res;
        if (!v)
            return res;
        if (!v->left && !v->right){
            for (int i = 0; i < get_count(v); ++i)
                res.push_back(0);
            return res;
        }
        const auto &left = eval(v->left, digit - 1);
        const auto &right = eval(v->right, digit - 1);
        for (auto val : left)
            res.push_back(val);
        for (auto val : right)
            res.push_back(val + (INT(1) << digit));
        return res;
    }
    vector<INT> eval() const{
        auto res = eval(root, MAX_DIGIT - 1);
        for (auto &val : res)
            val ^= lazy;
        return res;
    }
    friend ostream &operator<<(ostream &os,
                               const BinaryTrie<INT, MAX_DIGIT> &bt){
        auto res = bt.eval();
        for (auto val : res)
            os << val << " ";
        return os;
    }
};

void solve(){
    int N;
    cin>>N;
    string S;
    cin>>S;
    vi cnt(26);
    BinaryTrie<int,30> BT;
    rep(i,N){
        cnt[S[i]-'A']++;
        BT.insert(i);
    }
    int d=0,ans=0;
    while(true){
        int x=cnt[(26-d)%26]+cnt[(28-d)%26]+cnt[(32-d)%26]+cnt[(45-d)%26];
        if(!x) break;
        ans++;
        int p=BT.get(BT.get_kth(x-1));
        cnt[S[p]-'A']--;
        BT.erase(p);
        int y=cnt[S[p]-'A'];
        d=(d+y)%26;
    }
    cout<<ans<<endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();
}

yukicoder

結果

テストケース

ソースコード