結果

問題 No.3081 Make Palindromic Multiple
ユーザー Rubikun
提出日時 2025-03-28 22:24:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,911 bytes
コンパイル時間 2,952 ms
コンパイル使用メモリ 219,828 KB
実行使用メモリ 244,652 KB
最終ジャッジ日時 2025-03-28 22:25:02
合計ジャッジ時間 7,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 2
other -- * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=2000005,INF=15<<26;
//int128

//https://kopricky.github.io/code/Misc/int128.html

// __int128の入出力

using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
    string s;
    is >> s;
    v = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
    }
    if (s[0] == '-') { v *= -1; }
    return is;
}

ostream& operator<<(ostream& os, const LL& v)
{
    if (v == 0) { return (os << "0"); }
    LL num = v;
    if (v < 0) {
        os << '-';
        num = -num;
    }
    string s;
    for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}

LL rui[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    clock_t start,endd;
    start=clock();
    
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    ll N;cin>>N;
    
    string S=to_string(N);
    string T=S;reverse(all(T));
    
    rui[0]=1;
    for(int i=1;i<MAX;i++){
        rui[i]=rui[i-1]*10%N;
    }
    
    LL K=rng()%(MAX/2);
    if(K<0) K+=(MAX/2);
    K+=(MAX/4);
    if(K&1) K++;
    
    LL now=stoll(T)*rui[K+si(S)]+stoll(S);
    now%=N;
    
    unordered_map<ll,ll> MA;
    vll X(5000000);
    vector<array<ll,3>> Y(5000000);
    
    for(ll t=0;t<5000000;t++){
        string A=to_string(t);
        while(si(A)<6) A="0"+A;
        LL sum=now;
        for(int i=0;i<6;i++){
            sum+=rui[K/2+si(S)+5-i]*(A[i]-'0');
            sum+=rui[K/2+si(S)-1-(5-i)]*(A[i]-'0');
        }
        sum%=N;
        //MA[(N-sum)%N]=t;
        X[t]=mp((N-sum)%N,t);
    }
    
    sort(all(X));
    
    for(ll t=0;t<5000000;t++){
        ll x=rng()%mod;
        if(x<0) x+=mod;
        string A=to_string(x);
        while(si(A)<9) A="0"+A;
        LL sum=0;
        ll ge=rng()%(K/8);
        if(ge<0) ge+=(K/8);
        ge+=15;
        for(int i=0;i<9;i++){
            sum+=rui[K/2+si(S)+8-i+ge]*(A[i]-'0');
            sum+=rui[K/2+si(S)-1-ge-(8-i)]*(A[i]-'0');
        }
        sum%=N;
        Y[t]={(ll)sum,ge,x};
    }
    
    sort(all(Y));
    
    int i=0;
    
    for(auto [sum,ge,x]:Y){
        while(i<si(X)&&X[i].fi<sum) i++;
        if(i<si(X)&&X[i].fi==sum){
            auto [va,t]=X[i];
            
            string B=to_string(t);
            while(si(B)<6) B="0"+B;
            //cout<<K<<endl;
            string A=to_string(x);
            while(si(A)<9) A="0"+A;
            
            cout<<10<<"\n";
            cout<<T<<" "<<1<<"\n";
            cout<<0<<" "<<(K/2-(ge+9))<<"\n";
            cout<<A<<" "<<1<<"\n";
            cout<<0<<" "<<ge-6<<"\n";
            cout<<B<<" "<<1<<"\n";
            
            reverse(all(A));
            reverse(all(B));
            
            cout<<B<<" "<<1<<"\n";
            cout<<0<<" "<<ge-6<<"\n";
            cout<<A<<" "<<1<<"\n";
            cout<<0<<" "<<(K/2-(ge+9))<<"\n";
            cout<<S<<" "<<1<<"\n";
            
            return 0;
        }
    }
    
}
0