#936394 (C++17) No.2577 Simple Permutation Guess

提出ソース

結果

問題	No.2577 Simple Permutation Guess
ユーザー	Rubikun
提出日時	2023-12-05 00:21:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	13,230 bytes
コンパイル時間	3,375 ms
コンパイル使用メモリ	230,592 KB
実行使用メモリ	38,548 KB
平均クエリ数	0.07
最終ジャッジ日時	2023-12-05 00:21:57
合計ジャッジ時間	7,291 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 24,000 KB
testcase_01	TLE	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
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	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-
testcase_71	--	-
testcase_72	--	-
testcase_73	--	-
testcase_74	--	-
testcase_75	--	-
testcase_76	--	-
testcase_77	--	-
testcase_78	--	-
testcase_79	--	-
testcase_80	--	-
testcase_81	--	-
testcase_82	--	-
testcase_83	--	-
testcase_84	--	-
testcase_85	--	-
testcase_86	--	-
testcase_87	--	-
testcase_88	--	-
testcase_89	--	-
testcase_90	--	-
testcase_91	--	-
testcase_92	--	-
testcase_93	--	-
testcase_94	--	-
testcase_95	--	-
testcase_96	--	-
testcase_97	--	-
testcase_98	--	-
testcase_99	--	-
testcase_100	--	-
testcase_101	--	-
evil_1_rnd_1.txt	--	-
evil_1_rnd_2.txt	--	-
evil_2_big_1.txt	--	-
evil_2_big_2.txt	--	-
evil_2_big_3.txt	--	-
evil_3_sorted_1.txt	--	-
evil_4_sorted_rev_1.txt	--	-
evil_4_sorted_rev_2.txt	--	-
evil_400_sorted.txt	--	-
evil_400_sorted_rev.txt	--	-

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

ソースコード

raw source code

#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 all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

//多倍長

// https://github.com/beet-aizu/library/blob/master/tools/bigint.cpp

namespace FFT{
    using dbl = double;
    
    struct num{
        dbl x,y;
        num(){x=y=0;}
        num(dbl x,dbl y):x(x),y(y){}
    };
    
    inline num operator+(num a,num b){
        return num(a.x+b.x,a.y+b.y);
    }
    inline num operator-(num a,num b){
        return num(a.x-b.x,a.y-b.y);
    }
    inline num operator*(num a,num b){
        return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
    }
    inline num conj(num a){
        return num(a.x,-a.y);
    }
    
    int base=1;
    vector<num> rts={{0,0},{1,0}};
    vector<int> rev={0,1};
    
    const dbl PI=asinl(1)*2;
    
    void ensure_base(int nbase){
        if(nbase<=base) return;
        
        rev.resize(1<<nbase);
        for(int i=0;i<(1<<nbase);i++)
            rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));
        
        rts.resize(1<<nbase);
        while(base<nbase){
            dbl angle=2*PI/(1<<(base+1));
            for(int i=1<<(base-1);i<(1<<base);i++){
                rts[i<<1]=rts[i];
                dbl angle_i=angle*(2*i+1-(1<<base));
                rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
            }
            base++;
        }
    }
    
    void fft(vector<num> &as){
        int n=as.size();
        assert((n&(n-1))==0);
        
        int zeros=__builtin_ctz(n);
        ensure_base(zeros);
        int shift=base-zeros;
        for(int i=0;i<n;i++)
            if(i<(rev[i]>>shift))
                swap(as[i],as[rev[i]>>shift]);
        
        for(int k=1;k<n;k<<=1){
            for(int i=0;i<n;i+=2*k){
                for(int j=0;j<k;j++){
                    num z=as[i+j+k]*rts[j+k];
                    as[i+j+k]=as[i+j]-z;
                    as[i+j]=as[i+j]+z;
                }
            }
        }
    }
    
    template<typename T>
    vector<long long> multiply(vector<T> &as,vector<T> &bs){
        int need=as.size()+bs.size()-1;
        int nbase=0;
        while((1<<nbase)<need) nbase++;
        ensure_base(nbase);
        
        int sz=1<<nbase;
        vector<num> fa(sz);
        for(int i=0;i<sz;i++){
            T x=(i<(int)as.size()?as[i]:0);
            T y=(i<(int)bs.size()?bs[i]:0);
            fa[i]=num(x,y);
        }
        fft(fa);
        
        num r(0,-0.25/sz);
        for(int i=0;i<=(sz>>1);i++){
            int j=(sz-i)&(sz-1);
            num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
            if(i!=j)
                fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
            fa[i]=z;
        }
        fft(fa);
        
        vector<long long> res(need);
        for(int i=0;i<need;i++)
            res[i]=round(fa[i].x);
        
        return res;
    }
    
};
//BEGIN CUT HERE
struct bigint {
    using ll = long long;
    using vll = vector<ll>;
    
    inline static constexpr ll base_digits = 9;
    inline static constexpr ll base = 1000000000;
    
    vll a;
    ll sign;
    
    bigint():sign(1){}
    
    bigint(ll v){*this=v;}
    
    bigint(const string &s){read(s);}
    
    static bigint add_identity(){return bigint(0);}
    static bigint mul_identity(){return bigint(1);}
    
    void operator=(ll v){
        sign=1;
        if(v<0) sign=-1,v=-v;
        for(;v>0;v=v/base) a.emplace_back(v%base);
    }
    
    bigint operator+(const bigint &v) const{
        if(sign==v.sign){
            bigint res=v;
            for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size()) or carry;++i){
                if(i==(ll)res.a.size()) res.a.emplace_back(0);
                res.a[i]+=carry+(i<(ll)a.size()?a[i]:0);
                carry=res.a[i]>=base;
                if(carry) res.a[i]-=base;
            }
            return res;
        }
        return *this-(-v);
    }
    
    bigint operator-(const bigint &v) const{
        if(sign==v.sign){
            if(abs()>=v.abs()){
                bigint res=*this;
                for(ll i=0,carry=0;i<(ll)v.a.size() or carry;++i){
                    res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0);
                    carry=res.a[i]<0;
                    if(carry) res.a[i]+=base;
                }
                res.trim();
                return res;
            }
            return -(v-*this);
        }
        return *this+(-v);
    }
    
    void operator*=(ll v){
        if(v<0) sign=-sign,v=-v;
        for(ll i=0,carry=0;i<(ll)a.size() or  carry;++i){
            if(i ==(ll)a.size()) a.emplace_back(0);
            ll cur=a[i] *(ll)v+carry;
            carry=(ll)(cur/base);
            a[i]=(ll)(cur%base);
            // asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base));
        }
        trim();
    }
    
    bigint operator*(ll v) const{
        bigint res=*this;
        res*=v;
        return res;
    }
    
    friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){
        ll norm=base/(b1.a.back()+1);
        bigint a=a1.abs()*norm;
        bigint b=b1.abs()*norm;
        bigint q,r;
        q.a.resize(a.a.size());
        
        for(ll i=a.a.size()-1;i>=0;i--){
            r *=base;
            r+=a.a[i];
            ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()];
            ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1];
            ll d=((ll)base*s1+s2)/b.a.back();
            r-=b*d;
            while(r<0) r+=b,--d;
            q.a[i]=d;
        }
        
        q.sign=a1.sign*b1.sign;
        r.sign=a1.sign;
        q.trim();
        r.trim();
        return make_pair(q,r/norm);
    }
    
    bigint operator/(const bigint &v) const{
        return divmod(*this,v).first;
    }
    
    bigint operator%(const bigint &v) const{
        return divmod(*this,v).second;
    }
    
    void operator/=(ll v){
        if(v<0) sign=-sign,v=-v;
        for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){
            ll cur=a[i]+rem *(ll)base;
            a[i]=(ll)(cur/v);
            rem=(ll)(cur%v);
        }
        trim();
    }
    
    bigint operator/(ll v) const{
        bigint res=*this;
        res/=v;
        return res;
    }
    
    ll operator%(ll v) const{
        if(v<0) v=-v;
        ll m=0;
        for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m*(ll)base)%v;
        return m*sign;
    }
    
    void operator+=(const bigint &v){
        *this=*this+v;
    }
    
    void operator-=(const bigint &v){
        *this=*this-v;
    }
    
    void operator*=(const bigint &v){
        *this=*this*v;
    }
    
    void operator/=(const bigint &v){
        *this=*this/v;
    }
    
    bool operator<(const bigint &v) const{
        if(sign!=v.sign) return sign<v.sign;
        if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign;
        for(ll i=a.size()-1;i>=0;i--)
            if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign;
        return false;
    }
    
    bool operator>(const bigint &v) const{
        return v<*this;
    }
    
    bool operator<=(const bigint &v) const{
        return !(v<*this);
    }
    
    bool operator>=(const bigint &v) const{
        return !(*this<v);
    }
    
    bool operator==(const bigint &v) const{
        return !(*this<v) and !(v<*this);
    }
    
    bool operator!=(const bigint &v) const{
        return *this<v or v<*this;
    }
    
    void trim(){
        while(!a.empty() and !a.back()) a.pop_back();
        if(a.empty()) sign=1;
    }
    
    bool isZero() const{
        return a.empty() or (a.size()==1 and !a[0]);
    }
    
    bigint operator-() const{
        bigint res=*this;
        res.sign=-sign;
        return res;
    }
    
    bigint abs() const{
        bigint res=*this;
        res.sign*=res.sign;
        return res;
    }
    
    ll longValue() const{
        ll res=0;
        for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i];
        return res*sign;
    }
    
    friend bigint gcd(const bigint &a,const bigint &b){
        return b.isZero()?a:gcd(b,a%b);
    }
    
    friend bigint lcm(const bigint &a,const bigint &b){
        return a/gcd(a,b)*b;
    }
    
    void read(const string &s){
        sign=1;
        a.clear();
        ll pos=0;
        while(pos<(ll)s.size() and (s[pos]=='-' or s[pos]=='+')){
            if(s[pos]=='-') sign=-sign;
            ++pos;
        }
        for(ll i=s.size()-1;i>=pos;i-=base_digits){
            ll x=0;
            for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0';
            a.emplace_back(x);
        }
        trim();
    }
    
    friend istream &operator>>(istream &stream,bigint &v){
        string s;
        stream>>s;
        v.read(s);
        return stream;
    }
    
    friend ostream &operator<<(ostream &stream,const bigint &v){
        if(v.sign==-1) stream<<'-';
        stream<<(v.a.empty()?0:v.a.back());
        for(ll i=(ll)v.a.size()-2;i>=0;--i)
            stream<<setw(base_digits)<<setfill('0')<<v.a[i];
        return stream;
    }
    
    static vll convert_base(const vll &a,ll old_digits,ll new_digits){
        vll p(max(old_digits,new_digits)+1);
        p[0]=1;
        for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10;
        vll res;
        ll cur=0;
        ll cur_digits=0;
        for(ll i=0;i<(ll)a.size();i++){
            cur+=a[i]*p[cur_digits];
            cur_digits+=old_digits;
            while(cur_digits>=new_digits){
                res.emplace_back(signed(cur%p[new_digits]));
                cur/=p[new_digits];
                cur_digits-=new_digits;
            }
        }
        res.emplace_back((signed)cur);
        while(!res.empty() and !res.back()) res.pop_back();
        return res;
    }
    
    static vll karatsubaMultiply(vll &a,vll &b){
        {
            while(a.size()<b.size()) a.emplace_back(0);
            while(b.size()<a.size()) b.emplace_back(0);
            while(a.size()&(a.size()-1)) a.emplace_back(0),b.emplace_back(0);
        }
        
        ll n=a.size();
        vll res(n+n);
        if(n<=32){
            for(ll i=0;i<n;i++)
                for(ll j=0;j<n;j++)
                    res[i+j]+=a[i]*b[j];
            return res;
        }
        
        ll k=n>>1;
        vll a1(a.begin(),a.begin()+k);
        vll a2(a.begin()+k,a.end());
        vll b1(b.begin(),b.begin()+k);
        vll b2(b.begin()+k,b.end());
        
        vll a1b1=karatsubaMultiply(a1,b1);
        vll a2b2=karatsubaMultiply(a2,b2);
        
        for(ll i=0;i<k;i++) a2[i]+=a1[i];
        for(ll i=0;i<k;i++) b2[i]+=b1[i];
        
        vll r=karatsubaMultiply(a2,b2);
        for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i];
        for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i];
        
        for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i];
        for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i];
        for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i];
        return res;
    }
    
    bigint operator*(const bigint &v) const{
        constexpr static ll nbase = 10000;
        constexpr static ll nbase_digits = 4;
        
        vll a=convert_base(this->a,base_digits,nbase_digits);
        vll b=convert_base(v.a,base_digits,nbase_digits);
        
        if(a.empty() or b.empty()) return bigint(0);
        
        vll c=karatsubaMultiply(a,b);
        // vll c=FFT::multiply(a,b);
        
        bigint res;
        res.sign=sign*v.sign;
        for(ll i=0,carry=0;i<(ll)c.size();i++){
            ll cur=c[i]+carry;
            res.a.emplace_back((ll)(cur%nbase));
            carry=(ll)(cur/nbase);
            if(i+1==(int)c.size() and carry>0) c.emplace_back(0);
        }
        
        res.a=convert_base(res.a,nbase_digits,base_digits);
        res.trim();
        return res;
    }
};
//END CUT HERE

bigint fac[405];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    fac[0]=1;
    for(int i=1;i<=400;i++) fac[i]=fac[i-1]*i;
    
    int N;cin>>N;
    
    auto f=[&](bigint K){
        vector<int> ask,rem(N);iota(all(rem),1);
        for(int i=N-1;i>=0;i--){
            bigint po=K/fac[i];
            ask.push_back(rem[po.longValue()]);
            rem.erase(rem.begin()+po.longValue());
            K-=fac[i]*po;
        }
        cout<<"?";
        for(int a:ask) cout<<" "<<a;
        cout<<endl;
        int re;cin>>re;
        return re;
    };
    
    auto g=[&](bigint K){
        vector<int> ask,rem(N);iota(all(rem),1);
        for(int i=N-1;i>=0;i--){
            bigint po=K/fac[i];
            ask.push_back(rem[po.longValue()]);
            rem.erase(rem.begin()+po.longValue());
            K-=fac[i]*po;
        }
        cout<<"!";
        for(int a:ask) cout<<" "<<a;
        cout<<endl;
    };
    bigint left=0,right=fac[N];
    while(right-left>1){
        bigint mid=(left+right)/2;
        bool res=f(mid);
        if(res) left=mid;
        else right=mid;
    }
    
    g(left);
}

yukicoder

結果

テストケース

ソースコード