結果
問題 | No.397 NO MORE KADOMATSU |
ユーザー | btk |
提出日時 | 2016-07-16 19:45:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 1,721 ms |
コンパイル使用メモリ | 174,528 KB |
実行使用メモリ | 24,384 KB |
平均クエリ数 | 29.17 |
最終ジャッジ日時 | 2023-09-24 00:21:46 |
合計ジャッジ時間 | 3,384 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 29 ms
23,400 KB |
testcase_01 | AC | 25 ms
8,052 KB |
testcase_02 | AC | 24 ms
23,796 KB |
testcase_03 | AC | 25 ms
24,264 KB |
testcase_04 | AC | 25 ms
24,024 KB |
testcase_05 | AC | 26 ms
24,012 KB |
testcase_06 | AC | 25 ms
23,388 KB |
testcase_07 | AC | 25 ms
24,180 KB |
testcase_08 | AC | 25 ms
23,532 KB |
testcase_09 | AC | 25 ms
23,520 KB |
testcase_10 | AC | 25 ms
23,388 KB |
testcase_11 | AC | 25 ms
24,312 KB |
testcase_12 | AC | 25 ms
23,364 KB |
testcase_13 | AC | 25 ms
23,544 KB |
testcase_14 | AC | 25 ms
24,312 KB |
testcase_15 | AC | 26 ms
24,168 KB |
testcase_16 | AC | 25 ms
24,384 KB |
testcase_17 | AC | 24 ms
23,604 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; vector<P> mysort(vector<int> A,int m){ vector<P> res; int N=A.size(); for(int i=0;i<N;i++)A[i]*=m; for(int i=0;i<N;i++){ int bottom=A[i],id=i; for(int j=N-1;j>i;j--) if(bottom>A[j]){ bottom=A[j]; id=j; } if(id!=i){ res.push_back(P(i,id)); swap(A[i],A[id]); } } return res; } void print(vector<P>& v){ cout<<v.size()<<endl; for(auto &p:v)cout<<p.first<<" "<<p.second<<endl; string s;cin>>s; } bool checkKadomatsu(int a,int b,int c){ return (a!=c&&((a>b&&b<c)||(a<b&&b>c))); } bool test(vector<P>& v,vector<int> A){ for(auto &it:v){ swap(A[it.first],A[it.second]); } int N=A.size(); for(int i=0;i+2<N;i++){ if(checkKadomatsu(A[i],A[i+1],A[i+2]))return false; } return true; } vector<P> unko(int N){ vector<P> res; for(int i=0;i+5<N;i+=6) res.push_back(P(i+3,i+5)); return res; } int main(){ int N;cin>>N; vector<int> A(N); for(auto &it:A)cin>>it; auto p=mysort(A,1); auto q=mysort(A,-1); if(p.size()<q.size())q=p; auto kuso=unko(N); if(test(kuso,A)&&kuso.size()<q.size())q=kuso; print(q); return 0; }