#1049018 (C++23) No.2089 置換の符号

提出ソース
結果

問題	No.2089 置換の符号
コンテスト
ユーザー	clever-elsie
提出日時	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
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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();
}
yukicoder

結果

ソースコード
