#974850 (C++23) No.2732 Similar Permutations

提出ソース

結果

問題	No.2732 Similar Permutations
ユーザー	nouka28
提出日時	2024-04-20 10:01:50
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	133 ms / 2,000 ms
コード長	11,141 bytes
コンパイル時間	6,846 ms
コンパイル使用メモリ	338,864 KB
実行使用メモリ	13,812 KB
最終ジャッジ日時	2024-10-12 05:29:39
合計ジャッジ時間	25,569 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 7,684 KB
testcase_01	AC	5 ms 7,784 KB
testcase_02	AC	75 ms 9,136 KB
testcase_03	AC	95 ms 10,692 KB
testcase_04	AC	34 ms 8,684 KB
testcase_05	AC	29 ms 8,352 KB
testcase_06	AC	24 ms 8,020 KB
testcase_07	AC	81 ms 10,216 KB
testcase_08	AC	39 ms 8,856 KB
testcase_09	AC	26 ms 8,352 KB
testcase_10	AC	115 ms 13,388 KB
testcase_11	AC	25 ms 7,980 KB
testcase_12	AC	116 ms 13,680 KB
testcase_13	AC	120 ms 13,552 KB
testcase_14	AC	117 ms 13,680 KB
testcase_15	AC	133 ms 13,676 KB
testcase_16	AC	121 ms 12,732 KB
testcase_17	AC	89 ms 12,832 KB
testcase_18	AC	108 ms 13,428 KB
testcase_19	AC	116 ms 13,676 KB
testcase_20	AC	116 ms 13,532 KB
testcase_21	AC	115 ms 13,552 KB
testcase_22	AC	70 ms 10,704 KB
testcase_23	AC	116 ms 13,680 KB
testcase_24	AC	74 ms 10,852 KB
testcase_25	AC	114 ms 13,676 KB
testcase_26	AC	99 ms 13,160 KB
testcase_27	AC	114 ms 13,680 KB
testcase_28	AC	93 ms 12,952 KB
testcase_29	AC	116 ms 13,556 KB
testcase_30	AC	87 ms 12,588 KB
testcase_31	AC	114 ms 13,556 KB
testcase_32	AC	109 ms 13,436 KB
testcase_33	AC	114 ms 13,812 KB
testcase_34	AC	81 ms 10,960 KB
testcase_35	AC	114 ms 13,680 KB
testcase_36	AC	110 ms 13,436 KB
testcase_37	AC	111 ms 13,680 KB
testcase_38	AC	101 ms 13,216 KB
testcase_39	AC	114 ms 13,552 KB
testcase_40	AC	101 ms 13,164 KB
testcase_41	AC	115 ms 13,680 KB
testcase_42	AC	88 ms 12,796 KB
testcase_43	AC	112 ms 13,556 KB
testcase_44	AC	69 ms 10,624 KB
testcase_45	AC	115 ms 13,680 KB
testcase_46	AC	109 ms 13,404 KB
testcase_47	AC	114 ms 13,676 KB
testcase_48	AC	76 ms 10,896 KB
testcase_49	AC	111 ms 13,808 KB
testcase_50	AC	71 ms 10,884 KB
testcase_51	AC	104 ms 13,552 KB
testcase_52	AC	94 ms 13,320 KB
testcase_53	AC	117 ms 13,684 KB
testcase_54	AC	120 ms 13,680 KB
testcase_55	AC	114 ms 13,680 KB
testcase_56	AC	117 ms 13,680 KB
testcase_57	AC	68 ms 10,576 KB
testcase_58	AC	86 ms 12,696 KB
testcase_59	AC	83 ms 12,636 KB
testcase_60	AC	71 ms 10,688 KB
testcase_61	AC	68 ms 10,604 KB
testcase_62	AC	99 ms 13,152 KB
testcase_63	AC	2 ms 6,816 KB
testcase_64	AC	1 ms 6,820 KB
testcase_65	AC	2 ms 6,816 KB
testcase_66	AC	2 ms 6,820 KB
testcase_67	AC	4 ms 7,952 KB
testcase_68	AC	4 ms 7,672 KB
testcase_69	AC	4 ms 7,612 KB
testcase_70	AC	4 ms 7,560 KB
testcase_71	AC	4 ms 7,676 KB
testcase_72	AC	4 ms 7,412 KB
testcase_73	AC	5 ms 7,596 KB
testcase_74	AC	4 ms 7,696 KB
testcase_75	AC	4 ms 7,560 KB
testcase_76	AC	4 ms 7,416 KB
testcase_77	AC	4 ms 7,480 KB
testcase_78	AC	4 ms 7,420 KB
testcase_79	AC	4 ms 7,476 KB
testcase_80	AC	4 ms 7,548 KB
testcase_81	AC	4 ms 7,536 KB
testcase_82	AC	4 ms 7,516 KB
testcase_83	AC	4 ms 7,596 KB
testcase_84	AC	4 ms 7,584 KB
testcase_85	AC	4 ms 7,580 KB
testcase_86	AC	4 ms 7,528 KB
testcase_87	AC	4 ms 7,636 KB
testcase_88	AC	4 ms 7,636 KB
testcase_89	AC	4 ms 7,700 KB
testcase_90	AC	4 ms 7,684 KB
testcase_91	AC	5 ms 7,408 KB
testcase_92	AC	5 ms 7,408 KB
testcase_93	AC	5 ms 7,712 KB
testcase_94	AC	5 ms 7,480 KB
testcase_95	AC	12 ms 7,412 KB
testcase_96	AC	12 ms 7,600 KB
testcase_97	AC	13 ms 7,652 KB
testcase_98	AC	12 ms 7,652 KB
testcase_99	AC	16 ms 7,552 KB
testcase_100	AC	16 ms 7,652 KB
testcase_101	AC	16 ms 7,556 KB
testcase_102	AC	16 ms 7,476 KB

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

ソースコード

raw source code

#pragma region template
#include<bits/stdc++.h>
using namespace std;
//other
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
#include<atcoder/all>
using namespace atcoder;
// #include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
using zint = atcoder::modint1000000007;
// using mint=modint;
#define int long long
#define pb push_back
#define eb emplace_back
#define ep emplace
#define len(a) (int)a.size()
#define BIT(a,b) ((a)>>(b)&1)
// #define endl "\n"

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

//using 
using ll=long long;
using i32=signed;
using i64=long long;
using i128=__int128_t;
using ld=long double;
using ull=unsigned long long;
using uint=unsigned;
using pcc=pair<char,char>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<ld,ld>;
using vi=vector<int>;
using vl=vector<ll>;
using vvi=vector<vi>;
using vvl=vector<vl>;
using vvvi=vector<vvi>;
using vvvl=vector<vvl>;
template<class T>using V=vector<T>;
template<class T>using VV=vector<V<T>>;
template<class T>using VVV=vector<VV<T>>;
template<class T>using VVVV=vector<VVV<T>>;
template<class T>using VVVVV=vector<VVVV<T>>;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
template<class T>using pqmax=priority_queue<T>;
// template<class T>using pbds=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define chmax(a,b) (a)=max((a),(b))
#define chmin(a,b) (a)=min((a),(b))

const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=998244353;
const int MOD2=1000000007;
const ld PI=3.1415926535897932384626433832795028841971;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ll di[]={0,1,0,-1,1,-1,1,-1};
const ll dj[]={1,0,-1,0,1,1,-1,-1};

template<class T>
constexpr auto min(T a,T b,T c){
    return min(a,min(b,c));
}
template<class... T>
constexpr auto min(T... a){
    return min(initializer_list<common_type_t<T...>>{a...});
}

template<class T>
constexpr auto max(T a,T b,T c){
    return max(a,max(b,c));
}

template<class... T>
constexpr auto max(T... a){
    return max(initializer_list<common_type_t<T...>>{a...});
}

#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name

#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)

#define rrep1(n)for(ll i=n;i--;)
#define rrep2(i,n)for(ll i=n;i--;)
#define rrep3(i,a,b)for(ll i=b;i-->(a);)
#define rrep4(i,a,b,c)for(ll=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrpe4,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define isum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__),0_M)
#define elif else if

#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)

//io
//in
void scan(){}
void scan(signed &a){cin>>a;}
void scan(unsigned &a){cin>>a;}
void scan(long& a){cin>>a;}
void scan(long long& a){cin>>a;}
void scan(unsigned long long&a){cin>>a;}
void scan(char& a){cin>>a;}
void scan(float& a){cin>>a;}
void scan(double& a){cin>>a;}
void scan(long double& a){cin>>a;}
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){cin>>a;}
template<class T> void scan(vector<T>&);
template<class T, int size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, int size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, int size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, int size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void input(){}
template<class Head,class...Tail> void input(Head& head,Tail&... tail){scan(head);input(tail...);}
//out
void puts(){ putchar(' '); }
void puts(bool a){ printf("%d", a); }
void puts(signed a){ printf("%d", a); }
void puts(unsigned a){ printf("%u", a); }
void puts(long a){ printf("%ld", a); }
void puts(long long a){ printf("%lld", a); }
void puts(unsigned long long a){ printf("%llu", a); }
void puts(char a){ printf("%c", a); }
void puts(char a[]){ printf("%s", a); }
// void puts(const char a[]){ printf("%s", a); }
void puts(float a){ printf("%.15f", a); }
void puts(double a){ printf("%.15f", a); }
void puts(long double a){ printf("%.15Lf", a); }
void puts(const string& a){ for(auto&& i : a) puts(i); }
template<class T> void puts(const complex<T>& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); }
template<class T> void puts(const vector<T>&);
template<class T, int size> void puts(const array<T, size>&);
template<class T, class L> void puts(const pair<T, L>& p);
template<class T, int size> void puts(const T (&)[size]);
template<class T> void puts(const vector<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const deque<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const set<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const multiset<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T, int size> void puts(const array<T, size>& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T, class L> void puts(const pair<T, L>& p){ putchar('(');puts(p.first); putchar(' '); puts(p.second); putchar(')');}
template<class T, int size> void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const T& a){ cout << a; }
int print(){ putchar('\n'); return 0; }
template<class T> int print(const T& t){ puts(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; }
#pragma endregion

#pragma region commonly used
int digitsum(string s){
    int res=0;
    rep(i,(int)s.size()){
        res+=s[i]-'0';
    }
    return res;
}

//乱数系
random_device rnd; 
mt19937 mt(rnd());
const long long MT_MAX=LINF;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
    return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
    // [a,b]の乱数を生成
    return a+rd(mt)%(b-a+1);
}

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

__int128 parse(string &s) {
    __int128 ret = 0;
    for (int i = 0; i < (int)s.length(); i++)
        if ('0' <= s[i] && s[i] <= '9')
        ret = 10 * ret + s[i] - '0';
    return ret;
}

#define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__}))
vector<vector<long long>> __MAKE_MAT__(vector<long long> v){
    if(v.empty())return vector<vector<long long>>(1,vector<long long>());
    long long n=v.back();
    v.pop_back();
    vector<vector<long long>> ret;
    vector<vector<long long>> tmp=__MAKE_MAT__(v);
    for(auto e:tmp)for(long long i=0;i<n;++i){
        ret.push_back(e);
        ret.back().push_back(i);
    }
    return ret;
}

//V',Pを返す。PはVを昇順に並べた時のidx
template<class T>
pair<vector<T>,vector<int>> sortperm(vector<T> v){
    vector<pair<T,int>> sv;
    for(int i=0;i<(int)v.size();i++){
        sv.push_back({v[i],i});
    }
    sort(sv.begin(),sv.end());
    vector<T> rv;vector<int> p;
    for(auto[x,idx]:sv){
        rv.push_back(x);p.push_back(idx);
    }
    return {rv,p};
}

bool isdigit(char x){return '0'<=x&&x<='9';}
string ch_to_str(char x){return string{x};}
bool isupper(char x){return('A'<=x&&x<='Z');}
bool islower(char x){return('a'<=x&&x<='z');}
bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;}
// #include<boost/multiprecision/cpp_int.hpp>
// using lint=boost::multiprecision::cpp_int;

#pragma endregion


signed main(){
    INT(n);
    if(n==1){
        print(-1);
        return 0;
    }
    vi a(n);input(a);
    vi cnt(1<<19,-1);
    int t=0;
    vi p;rep(i,n)p.pb(i+1);
    int val=0;rep(i,n)val^=a[i]+p[i];
    auto next_perm=[&](vi &tp,int &tval) {
        // print('N',tp,tval);
        int idx=n-2;
        while(idx>=0&&tp[idx]>tp[idx+1])idx--;
        if(idx<0){
            return;
        }
        // print("idx",idx);
        tval^=(a[idx]+tp[idx]);
        int idx2=n-1;
        while(idx2>=0&&tp[idx2]<=tp[idx])idx2--;
        if(idx2<=idx)return;
        tval^=(a[idx2]+tp[idx2]);
        swap(tp[idx],tp[idx2]);
        tval^=(a[idx]+tp[idx]);
        tval^=(a[idx2]+tp[idx2]);
        rep(i,idx+1,n)tval^=a[i]+tp[i];
        reverse(tp.begin()+idx+1,tp.end());
        rep(i,idx+1,n)tval^=a[i]+tp[i];
        // print('!');
    };

    int f=1;rep(i,1,n+1)f=min(f*i,1<<19);
    int v1=-1,v2=-1;
    rep(i,f){
        // print(i,':',p);
        // int xsm=0;rep(i,n)xsm^=(a[i]+p[i]);
        // print(val,xsm);
        if(cnt[val]!=-1){
            v1=cnt[val],v2=i;
            // break;
        }else{
            cnt[val]=i;
        }
        if(i!=f-1)next_perm(p,val);
    }
    // print('V',v1,v2);
    // return 0;
    if(v1==-1){
        print(-1);
        exit(0);
    }else{
        vi rp;rep(i,n)rp.pb(i+1);
        rep(i,f){
            if(i==v1){
                print(rp);
                // int xsm=0;rep(i,n)xsm^=(rp[i]+a[i]);
                // print(xsm);
            }
            else if(i==v2){
                print(rp);
                // int xsm=0;rep(i,n)xsm^=(rp[i]+a[i]);
                // print(xsm);
            }
            next_permutation(rp.begin(),rp.end());
        }   
    }
}

yukicoder

結果

テストケース

ソースコード