結果
| 問題 |
No.2589 Prepare Integers
|
| コンテスト | |
| ユーザー |
 Newtech66
|
| 提出日時 | 2024-08-25 16:50:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,118 bytes |
| コンパイル時間 | 2,842 ms |
| コンパイル使用メモリ | 231,036 KB |
| 最終ジャッジ日時 | 2025-02-24 02:02:57 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | TLE * 1 -- * 23 |
コンパイルメッセージ
In file included from /usr/include/c++/13/istream:41,
from /usr/include/c++/13/sstream:40,
from /usr/include/c++/13/complex:45,
from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
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:
/usr/include/c++/13/ostream:204:25: warning: ‘ans’ may be used uninitialized [-Wmaybe-uninitialized]
204 | { 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;
| ^~~
ソースコード
#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;
}