結果

問題 No.2589 Prepare Integers
ユーザー Newtech66Newtech66
提出日時 2024-08-25 16:49:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,130 bytes
コンパイル時間 2,942 ms
コンパイル使用メモリ 238,764 KB
実行使用メモリ 13,888 KB
最終ジャッジ日時 2024-08-25 16:49:44
合計ジャッジ時間 6,779 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,888 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 3 ms
6,944 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In member function 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]',
    inlined from 'void solve()' at main.cpp:169:19:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:202:25: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized]
  202 |       { return _M_insert(__n); }
      |                ~~~~~~~~~^~~~~
main.cpp: In function 'void solve()':
main.cpp:159:44: note: 'ans' was declared here
  159 |             lol l = 1, r = L.total(), mid, ans;
      |                                            ^~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

pair<lol,lol> exgcd(lol a,lol b){
    if(b == 0){
        return make_pair(1, 0);
    }
    auto [x1, y1] = exgcd(b, a % b);
    lol x = y1;
    lol y = x1 - y1 * (a / b);
    return make_pair(x, y);
}

struct LinearBasis{
    static const int d = 65;
    lol mod;
    struct Vector{
        lol mod;
        vector<lol> vec;
        Vector(lol v, lol m):mod(m){
            vec.resize(d, 0);
            vector<lol> t;
            while(v){
                t.push_back(v % mod);
                v /= mod;
            }
            for(int i=0;i<(int)t.size();i++){
                vec[d-1-i] = t[i];
            }
        }
        lol to_number(){
            lol R = 0;
            for(int i=0;i<d;i++){
                R = mod * R + vec[i];
            }
            return R;
        }
        lol operator[](int p){return vec[p];}
        const lol operator[](int p) const{return vec[p];}
        Vector& operator+=(const Vector& other){
            for(int i=0;i<d;i++){
                this->vec[i] += other.vec[i] % mod;
                this->vec[i] %= mod;
            }
            return *this;
        }
        friend Vector operator+(Vector lhs, const Vector& rhs){
            lhs += rhs;
            return lhs;
        }
        Vector& operator-=(const Vector& other){
            for(int i=0;i<d;i++){
                this->vec[i] -= other.vec[i] % mod;
                this->vec[i] = (this->vec[i] + mod) % mod;
            }
            return *this;
        }
        friend Vector operator-(Vector lhs, const Vector& rhs){
            lhs -= rhs;
            return lhs;
        }
        Vector& operator*=(const lol& scalar){
            for(int i=0;i<d;i++){
                this->vec[i] *= scalar % mod;
                this->vec[i] %= mod;
            }
            return *this;
        }
        friend Vector operator*(Vector lhs, const lol& rhs){
            lhs *= rhs;
            return lhs;
        }
        friend Vector operator*(const lol& rhs, Vector lhs){
            lhs *= rhs;
            return lhs;
        }
    };
    vector<Vector> A;   //this is the basis
    Vector vec(lol v){
        return Vector(v, mod);
    }
    LinearBasis(lol m): mod(m){A.resize(d,vec(0));}
    void add(Vector V){
        for(int i=0;i<d;i++){
            if(V[i] != 0){
                if(A[i][i] == 0){
                    auto [s,t] = exgcd(V[i], mod);
                    // s = (s % mod + mod)%mod;
                    // t = (t % mod + mod)%mod;
                    A[i] = V * s;
                    V = V * (mod / A[i][i]);
                }else if(V[i] % A[i][i] == 0){
                    V -= A[i] * (V[i] / A[i][i]);
                }else{
                    auto W = A[i];
                    auto [s,t] = exgcd(V[i], W[i]);
                    // s = (s % mod + mod)%mod;
                    // t = (t % mod + mod)%mod;
                    A[i] = V * s + W * t;
                    V -= A[i] * (V[i] / A[i][i]);
                    W -= A[i] * (W[i] / A[i][i]);
                    add(W);
                }
            }
        }
    }
    lol total(){
        lol B = 1;
        for(int i=0;i<d;i++){
            if(A[i][i]) B *= mod / A[i][i];
        }
        return B;
    }
    lol kth(lol k){
        lol B = total();
        if(k > B)   return -1;
        auto R = vec(0);
        for(int i=0;i<d;i++){
            if(!A[i][i])    continue;
            B /= mod / A[i][i];
            lol l = min((k - 1) / B, mod / A[i][i] - 1);
            lol q = (R[i] / A[i][i]) % (mod / A[i][i]);
            q = (l - q + mod / A[i][i]) % (mod / A[i][i]);
            k -= l * B;
            R += A[i] * q;
        }
        return R.to_number();
    }
};

void solve(){
    lol k;
    int q;
    cin>>k>>q;
    auto L = LinearBasis(k);
    while(q--){
        int t;
        lol x;
        cin>>t>>x;
        if(t==1){
            L.add(L.vec(x));
        }else if(t==2){
            cout<<L.kth(x)<<endl;
        }else{
            // You can find the kth smallest number
            lol l = 1, r = L.total(), mid, ans;
            while(l<=r){
                mid = l + (r - l) / 2;
                if(L.kth(mid) <= x){
                    l = mid + 1;
                    ans = mid;
                }else{
                    r = mid - 1;
                }
            }
            cout<<ans<<endl;
        }
    }
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
// cin>>_;
while(_--)
{
    solve();
}
return 0;
}
0