結果
問題 |
No.2089 置換の符号
|
ユーザー |
|
提出日時 | 2025-03-03 19:13:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 11,750 bytes |
コンパイル時間 | 3,112 ms |
コンパイル使用メモリ | 241,464 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-03-03 19:13:11 |
合計ジャッジ時間 | 3,992 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#ifndef ELSIE_LOCAL_H #define ELSIE_LOCAL_H #if __has_include(<atcoder/modint>) #include "atcoder/modint" using namespace atcoder; using mint=modint998244353; using mint1=modint1000000007; #endif #include <limits> #include <new> #include <initializer_list> #include <compare> #include <concepts> #include <utility> #include <bitset> #include <tuple> #include <type_traits> #include <functional> #include <chrono> #include <array> #include <deque> #include <list> #include <queue> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <iterator> #include <ranges> #include <algorithm> #include <bit> #include <random> #include <numeric> #include <numbers> #include <iostream> #include <ios> #include <streambuf> #include <iomanip> #include <sstream> #include <regex> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> using namespace std; using namespace chrono; namespace nbl=numbers; using std::cin; using std::cout; using sstream=stringstream; #define RET return #define fi first #define se second #define endl '\n' #define sn(i,c) " \n"[i==c] #define rsv(n) reserve(n) #define pf(a) push_front(a) #define pb(a) push_back(a) #define eb(...) emplace_back(__VA_ARGS__) #define ppf() pop_front() #define ppb() pop_back() #define pp() pop() #define ins(a) insert(a) #define emp(...) emplace(__VA_ARGS__) #define ers(a) erase(a) #define cont(a) contains(a) #define mp(f,s) make_pair(f,s) #define A(a) begin(a),end(a) #define I(a,i) begin(a),begin(a)+(i) #define elif(c) else if(c) #define _SEL4(_1,_2,_3,_4,name,...) name #define _SEL3(_1,_2,_3,name,...) name #define _REP4(i,s,n,st) for(int i=(s);i<(n);i+=(st)) #define _REP3(i,s,n) _REP4(i,s,n,1) #define _REP2(i,n) _REP3(i,0,n) #define _REP1(n) _REP2(_,n) #define _RREP4(i,n,t,s) for(int i=(n);i>=(t);i-=(s)) #define _RREP3(i,n,t) _RREP4(i,n,t,1) #define _RREP2(i,n) _RREP3(i,n,0) #define _ITER2(x,a) for(auto&x:a) #define _ITER3(x,y,a) for(auto&[x,y]:a) #define _CTER2(x,a) for(const auto&x:a) #define _CTER3(x,y,a) for(const auto&[x,y]:a) #define rep(...) _SEL4(__VA_ARGS__,_REP4,_REP3,_REP2,_REP1)(__VA_ARGS__) #define rrep(...) _SEL4(__VA_ARGS__,_RREP4,_RREP3,_RREP2,_REP1)(__VA_ARGS__) #define forif(c,...) rep(__VA_ARGS__)if(c) #define iter(...) _SEL3(__VA_ARGS__,_ITER3,_ITER2)(__VA_ARGS__) #define cter(...) _SEL3(__VA_ARGS__,_CTER3,_CTER2)(__VA_ARGS__) #define _LB_BEX(b,e,x) lower_bound(b,e,x) #define _LB_BEXG(b,e,x,g) lower_bound(b,e,x,g) #define _UB_BEX(b,e,x) upper_bound(b,e,x) #define _UB_BEXG(b,e,x,g) upper_bound(b,e,x,g) #define lb(...) _SEL4(__VA_ARGS__,_LB_BEXG,_LB_BEX)(__VA_ARGS__) #define ub(...) _SEL4(__VA_ARGS__,_UB_BEXG,_UB_BEX)(__VA_ARGS__) #define rev(a) reverse(A(a)) #define minel(a) min_element(A(a)) #define maxel(a) max_element(A(a)) #define acm(a) accumulate(A(a),0ll) #define nxpm(a) next_permutation(A(a)) #define Sort(a) sort(A(a)) #define uni(a) Sort(a);a.erase(unique(A(a)),a.end()) #define swapcase(a) a=(isalpha(a)?a^32:a) #define NL cout<<'\n' constexpr int64_t inf=1ll<<60,minf=-inf; constexpr int32_t inf32=1ll<<30,minf32=-inf32; constexpr char sep='\n'; constexpr array<pair<int32_t,int32_t>,8>dc={{{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}}; template<class T,class U>inline void chmax(T&a,const U&b){if(a<b)a=b;} template<class T,class U>inline void chmin(T&a,const U&b){if(a>b)a=b;} #define yes cout<<"Yes\n" #define no cout<<"No\n" #define yn(c) (c)?yes:no #if __cplusplus <= 202002L #else #define C const namespace vies=std::views; #define DR(i) views::drop(i) #define TK(i) views::take(i) #define RV views::reverse #define IOTA vies::iota #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define STR(...) str __VA_ARGS__;in(__VA_ARGS__) #define VI(a,n) vi a(n);in(a) #define VIT(a,n) vit a(n);in(a) #define VS(a,n) vs a(n);in(a) #define UV(u,v) INT(u,v);--u,--v #define UVW(u,v,w) INT(u,v,w);--u,--v template<class T,class U>concept LUBI= same_as<T,vector<U>>||same_as<T,deque<U>>||is_array_v<T>; #define TP template<class T,class U,typename cp=less<U>> #define RL requires LUBI<T,U> TP size_t lbi(C T&v,C U&x,cp cmp=cp())RL{RET lb(A(v),x,cmp)-begin(v);} TP size_t ubi(C T&v,C U&x,cp cmp=cp())RL{RET ub(A(v),x,cmp)-begin(v);} TP size_t lbi(size_t i,C T&v,C U&x,cp cmp=cp())RL{RET lb(i+A(v),x,cmp)-begin(v);} TP size_t ubi(size_t i,C T&v,C U&x,cp cmp=cp())RL{RET ub(i+A(v),x,cmp)-begin(v);} TP size_t lbi(C T&v,size_t i,C U&x,cp cmp=cp())RL{RET lb(I(v,i),x,cmp)-begin(v);} TP size_t ubi(C T&v,size_t i,C U&x,cp cmp=cp())RL{RET ub(I(v,i),x,cmp)-begin(v);} TP size_t lbi(size_t i,C T&v,size_t e,C U&x,cp cmp=cp())RL{RET lb(i+I(v,e),x,cmp)-begin(v);} TP size_t ubi(size_t i,C T&v,size_t e,C U&x,cp cmp=cp())RL{RET ub(i+I(v,e),x,cmp)-begin(v);} #undef TP #undef RL #define TP template #define MUT make_unsigned_t TP<integral T>int32_t pcnt(T p){return popcount(MUT<T>(p));} TP<integral T>int32_t lsb(T p){return countl_zero(MUT<T>(p));} TP<integral T>int32_t msb(T p){return countr_zero(MUT<T>(p));} TP<int32_t N,integral T>void putbit(T s){ char buf[N+1]={0}; for(char*itr=buf+N-1;itr>=buf;itr--,s>>=1) *itr='0'+(s&1); cout<<buf<<sep; } #undef MUT #undef TP #undef C #ifndef ELSIE_STD_IO #define ELSIE_STD_IO template<class T>concept Lint=is_integral_v<T>&&sizeof(T)>8; template<class T>concept Itrabl=requires(const T&x){x.begin();x.end();}&&!std::is_same_v<T,string>; template<class T>concept IItrabl=Itrabl<T>&&Itrabl<typename T::value_type>; template<class T>concept ModInt=requires(const T&x){x.val();}; template<class T>concept NLobj=Itrabl<T>||std::is_same_v<T,string>; istream&operator<<(istream&is,__float128&x){double y;is>>y;x=y;return is;} ostream&operator<<(ostream&os,const __float128&x){return os<<static_cast<double>(x);} template<Lint T>ostream&operator<<(ostream&dst,T val){ ostream::sentry s(dst); if(!s)return dst; char _O128[64]; char*d=end(_O128); bool vsign=val<0; __uint128_t v=val; if(vsign&&val!=numeric_limits<T>::min())v=1+~(__uint128_t)val; do{ *(--d)="0123456789"[v%10]; v/=10; }while(v!=0); if(vsign)*(--d)='-'; size_t len=end(_O128)-d; if(dst.rdbuf()->sputn(d,len)!=len)dst.setstate(ios_base::badbit); return dst; } template<Lint T>istream&operator>>(istream&src,T&val) { string s;src>>s; bool is_neg=numeric_limits<T>::is_signed&&s.size()>0&&s[0]=='-'; for(val=0;const auto&x:s|views::drop(is_neg))val=10*val+x-'0'; if(is_neg)val*=-1; return src; } template<ModInt T>istream&operator>>(istream&is,T&v){int64_t x;is>>x;v=x;return is;} template<class T,class U>istream&operator>>(istream&is,pair<T,U>&v){return is>>v.first>>v.second;} template<Itrabl T>istream&operator>>(istream&is,T&v){for(auto&&x:v)is>>x;return is;} template<class T>void in(T&a){cin>>a;} template<class T,class... Ts>void in(T&a,Ts&... b){in(a);in(b...);} template<class T,class U>vector<pair<T,U>>zip(size_t n,size_t m){ vector<pair<T,U>>r(min(n,m)); iter(x,y,r)in(x); iter(x,y,r)in(y); return move(r); } template<class T,class U>vector<pair<T,U>>zip(size_t n){return move(zip<T,U>(n,n));} template<ModInt T>ostream&operator<<(ostream&os,const T&v){return os<<v.val(); } template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>&v){return os<<'('<<v.first<<','<<v.second<<')';} template<Itrabl T>ostream&operator<<(ostream&os,const T&v){int cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?" ":"");return os;} template<IItrabl T>ostream&operator<<(ostream&os,const T&v){int cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?"\n":"");return os;} inline ostream*dos=&cout; inline int32_t OFLG; template<class T>void _out(const T&a){if(OFLG)(*dos)<<"0 \n"[OFLG]<<a;else(*dos)<<a;OFLG=1;} template<NLobj T>void _out(const T&a){(*dos)<<(OFLG?"\n":"")<<a;OFLG=2;} template<class T,class...Ts>void _out(const T&a,const Ts&... b){_out(a);_out(b...);} template<class... Ts>void out(const Ts&... v){OFLG=0;_out(v...);(*dos)<<sep;} #endif #endif #ifdef LOCAL #define dput(...) dos=&cerr;out(__VA_ARGS__);dos=&cout #else #define dput(...) #endif #endif #ifndef ELSIE_UNIONFIND #define ELSIE_UNIONFIND namespace elsie{ using namespace std; class unionFind{ protected: using it=int32_t; it _order; mutable vector<it>pr; public: unionFind():_order(0),pr(0){} unionFind(it n):_order(n),pr(n,-1){} it ord()const{return _order;} it size(it u)const{return -pr[root(u)];} it root(it u)const{return(pr[u]<0?u:pr[u]=root(pr[u]));} bool same(it u,it v)const{return root(u)==root(v);} void unite(it u,it v)const{ u=root(u),v=root(v); if(u==v)return; if(pr[u]<pr[v])swap(u,v); pr[v]+=pr[u]; pr[u]=v; } vector<vector<it>> groups()const{ vector<vector<it>>ret; unordered_map<it,it>idx; for(it i=0;i<_order;++i){ it r=root(i); auto itr=idx.find(r); if(itr==idx.end()){ idx[r]=ret.size(); ret.emplace_back(1,i); }else ret[itr->second].push_back(i); } return move(ret); } unionFind&operator=(auto&&other){ if(this!=&other){ _order=other._order; pr=forward(other.pr); }return*this; } }; template<class S,S(*op)(S,S),S(*e)()> class dsu:public unionFind{ private:vector<S>_mset; public: dsu():unionFind(),_mset(0){} dsu(int32_t n):unionFind(n),_mset(n,e()){} void set(int32_t u,const S&v){_mset[root(u)]=v;} S prod(int32_t u){return _mset[root(u)];} void unite(int32_t u,int32_t v){ int ru=root(u),rv=root(v); unionFind::unite(u,v); _mset[(ru==root(u)?ru:rv)]=op(_mset[ru],_mset[rv]); } }; template<class S>class unionFindP{ using it=int32_t; it _order; mutable vector<it>pr; mutable vector<S>pot; public: unionFindP():_order(0),pr(0),pot(0){} unionFindP(it n):_order(n),pr(n,-1),pot(n,S()){} it ord()const{return _order;} it size(it u)const{return -pr[root(u)];} bool same(it u,it v)const{return root(u)==root(v);} S potential(it u)const{root(u);return pot[u];} S diff(it u,it v)const{return potential(u)-potential(v);} it root(it u)const{ if(pr[u]<0)return u; it r=root(pr[u]); pot[u]+=pot[pr[u]]; return pr[u]=r; } bool unite(it u,it v,S w)const{ w+=potential(v)-potential(u); u=root(u),v=root(v); if(u==v)return w==S(); if(pr[u]<pr[v])swap(u,v),w=-w; pr[v]+=pr[u];pr[u]=v;pot[u]=w;return 1; } unionFindP&operator=(auto&&other){ if(this!=&other){ _order=other._order; pr=forward(other.pr); pot=forward(other.pot); }return*this; } }; } #endif #ifndef ELSIE_ALIAS #define ELSIE_ALIAS template<class f>using vc=vector<f>; template<class f>using vv=vc<vc<f>>; template<class f>using v3=vv<vc<f>>; template<class f>using v4=vv<vv<f>>; template<class f>using gr=greater<f>; template<class f>using pq=priority_queue<f>; template<class f>using pqg=priority_queue<f, vc<f>, gr<f>>; #define uset unordered_set #define umap unordered_map using it=int32_t; using i8=int8_t; using u8=uint8_t; using i16=int16_t; using u16=uint16_t; using i32=int32_t; using u32=uint32_t; using i64=int64_t; using u64=uint64_t; using i128=__int128_t; using u128=__uint128_t; using intw=__int128_t; using uintw=__uint128_t; using f32=float; using f64=double; using f128=__float128; using vi=vc<i64>; using vit=vc<it>; using vb=vc<bool>; using pi=pair<i64,i64>; using pit=pair<it,it>; using str=string; using vs=vc<str>; using pqgp=pqg<pi>; #define int i64 #define itn i64 #endif void slv(){ INT(n); VI(a,n); elsie::unionFind uf(n); rep(i,n){ --a[i]; uf.unite(i,a[i]); } umap<int,int>p; int ans=0; rep(i,n) if(uf.size(i)!=1) if(!p.cont(uf.root(i))){ p[uf.root(i)]=uf.size(i); ans+=uf.size(i)-1; } out(ans&1?-1:1); } signed main(){ cin.tie(0)->sync_with_stdio(0); cout<<fixed<<setprecision(15); slv(); }