Submission #64786

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
const char newl = '\n';
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
vector<T> ts(n);
for(size_t i=0;i<n;i++) cin>>ts[i];
return ts;
}
//INSERT ABOVE HERE
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin>>n;
auto hs=read(n);
for(int &h:hs) h--;
vector<int> used(n);
vector<int> odd,even;
for(int i=0;i<n;i++){
if(used[i]) continue;
int cur=i,len=0;
while(!used[cur]){
used[cur]=1;
cur=hs[cur];
len++;
}
if(len%2==0) even.emplace_back(len);
else odd.emplace_back(len);
}
int ans=0;
for(int len:odd)
ans+=(len-1)/2;
for(int len:even)
ans+=(len-2)/2;
if(even.size()&1) drop(-1);
ans+=even.size();
cout<<ans<<newl;
return 0;
}

ステータス

項目 データ
問題 1458 - ロボットアーム
ユーザー名 syoribu
投稿日時 2020-11-20 12:26:49
言語 C++17
状態 Accepted
得点 10
ソースコード長 1091 Byte
最大実行時間 40 ms
最大メモリ使用量 3432 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 22 ms 604 KB
1
in2 AC 18 ms 516 KB
1
in3 AC 20 ms 692 KB
1
in4 AC 19 ms 772 KB
1
in5 AC 31 ms 644 KB
1
in6 AC 24 ms 752 KB
1
in7 AC 22 ms 704 KB
1
in8 AC 25 ms 656 KB
1
in9 AC 19 ms 736 KB
1
in10 AC 29 ms 432 KB
1
in11 AC 24 ms 388 KB
1
in12 AC 20 ms 476 KB
1
in13 AC 17 ms 428 KB
1
in14 AC 24 ms 516 KB
1
in15 AC 23 ms 472 KB
1
in16 AC 23 ms 428 KB
1
in17 AC 24 ms 512 KB
1
in18 AC 18 ms 600 KB
1
in19 AC 20 ms 560 KB
1
in20 AC 17 ms 476 KB
1
in21 AC 21 ms 564 KB
1
in22 AC 20 ms 520 KB
1
in23 AC 24 ms 604 KB
1
in24 AC 18 ms 568 KB
1
in25 AC 27 ms 524 KB
1
in26 AC 30 ms 484 KB
1
in27 AC 17 ms 568 KB
1
in28 AC 20 ms 524 KB
1
in29 AC 23 ms 604 KB
1
in30 AC 17 ms 640 KB
1
in31 AC 20 ms 592 KB
1
in32 AC 20 ms 548 KB
1
in33 AC 31 ms 628 KB
1
in34 AC 23 ms 712 KB
1
in35 AC 25 ms 548 KB
1
in36 AC 20 ms 636 KB
1
in37 AC 29 ms 584 KB
1
in38 AC 19 ms 664 KB
1
in39 AC 18 ms 748 KB
1
in40 AC 29 ms 984 KB
1
in41 AC 21 ms 752 KB
1
in42 AC 20 ms 816 KB
1
in43 AC 35 ms 2300 KB
1
in44 AC 33 ms 3232 KB
1
in45 AC 37 ms 3380 KB
1
in46 AC 36 ms 2964 KB
1
in47 AC 32 ms 3380 KB
1
in48 AC 32 ms 2888 KB
1
in49 AC 40 ms 3432 KB
1
in50 AC 27 ms 3408 KB
1