Submission #00069
ソースコード
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include<bits/stdc++.h> #define rep(i,a,n) for(long long i=a;i<n;i++) #define repp(i,a,n) for(long long i=a;i>=n;i--) #define so(z) sort(z.begin(),z.end()) #define sor(z) sort(z.rbegin(),z.rend()) #define re(z) reverse(z.begin(),z.end()) #define su(a) substr(a) #define sub(a,b) substr(a,b) #define yess cout<<"YES"<<nn #define noo cout<<"NO"<<nn #define yes cout<<"Yes"<<"\n" #define no cout<<"No"<<"\n" #define yesr cout<<"Yes"<<"\n";return(0) #define nor cout<<"No"<<"\n";return(0) #define fi first #define se second #define fr() front() #define mp make_pair #define pb push_back #define nn "\n" #define ll long long #define mod 1000000007 #define IM INT_MAX #define LM LONG_LONG_MAX #define gcd(x,y) __gcd(x,y) //最大公約数 #define lcm(x,y) x/(__gcd(x,y))*y //最小公倍数 #define prev(a) prev_permutation(a.begin(),a.end()) //辞書前 #define next(a) next_permutation(a.begin(),a.end()) //辞書後 #define get(s) getline(cin,s) // 空白の空いたstringの入力 #define fixed(a) fixed<<setprecision(a) //小数点何桁か指定 #define ro(a) round(a) //四捨五入 #define ce(a) ceil(a) //切り上げ #define up(a,v) upper_bound(a.begin(),a.end(),v) #define lo(a,v) lower_bound(a.begin(),a.end(),v) #define bi(a,v) binary_bound(a.begin(),a.end(),v) using namespace std; int main(){ cin.tie(NULL); ios::sync_with_stdio( false ); ll n,q,ans=0; cin>>n; vector<ll>a(n),b; rep(i,0,n) cin>>a[i]; b=a; cin>>q; vector<ll>x(q),y(q); rep(i,0,q){ cin>>x[i]>>y[i]; x[i]--; y[i]--; } so(b); if (a==b){ cout<<0<<nn; return (0); } rep(i,0,n){ if (a[i]==b[i]) ans++; } rep(i,0,q){ if (a[x[i]]==b[x[i]]) ans--; if (a[y[i]]==b[y[i]]) ans--; if (a[x[i]]==b[y[i]]) ans++; if (a[y[i]]==b[x[i]]) ans++; if (ans==n){ cout<<i+1<<nn; return (0); } swap(a[x[i]],a[y[i]]); } cout<<-1<<nn; return (0); } |
ステータス
項目 | データ |
---|---|
問題 | 0006 - ボゾソート |
ユーザー名 | r2201 |
投稿日時 | 2023-07-24 09:54:20 |
言語 | C++17 |
状態 | Accepted |
得点 | 7 |
ソースコード長 | 2068 Byte |
最大実行時間 | 77 ms |
最大メモリ使用量 | 9940 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 7 / 7 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in1.txt | AC | 21 ms | 600 KB |
1
|
in2.txt | AC | 19 ms | 384 KB |
1
|
in3.txt | AC | 27 ms | 484 KB |
1
|
in4.txt | AC | 22 ms | 564 KB |
1
|
in5.txt | AC | 24 ms | 648 KB |
1
|
in6.txt | AC | 23 ms | 604 KB |
1
|
in7.txt | AC | 27 ms | 556 KB |
1
|
in8.txt | AC | 20 ms | 636 KB |
1
|
in9.txt | AC | 26 ms | 592 KB |
1
|
in10.txt | AC | 72 ms | 9768 KB |
1
|
in11.txt | AC | 76 ms | 9812 KB |
1
|
in12.txt | AC | 72 ms | 9860 KB |
1
|
in13.txt | AC | 74 ms | 9908 KB |
1
|
in14.txt | AC | 61 ms | 9828 KB |
1
|
in15.txt | AC | 63 ms | 9880 KB |
1
|
in16.txt | AC | 71 ms | 9924 KB |
1
|
in17.txt | AC | 69 ms | 9844 KB |
1
|
in18.txt | AC | 74 ms | 9892 KB |
1
|
in19.txt | AC | 77 ms | 9940 KB |
1
|
in20.txt | AC | 50 ms | 4696 KB |
1
|
in21.txt | AC | 44 ms | 2904 KB |
1
|
in22.txt | AC | 30 ms | 2888 KB |
1
|
in23.txt | AC | 72 ms | 7092 KB |
1
|
in24.txt | AC | 30 ms | 2000 KB |
1
|
in25.txt | AC | 72 ms | 7200 KB |
1
|
in26.txt | AC | 54 ms | 5232 KB |
1
|