提出 #23005615

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
ll dmod(ll x){
    return ((x+mod)%mod);
}
ll modular_power(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=dmod(ans*x);
        y/=2;
        x=dmod(x*x);
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int tc;
    cin>>tc;
    while(tc--){
        int n;
        cin>>n;
        int arr[n+1];
        for(int i=1;i<=n;i++)cin>>arr[i];
        set <int> even,odd;
        for(int i=1;i<n;i++){
            if(arr[i]>arr[i+1]){
                if(i&1)odd.insert(i);
                else even.insert(i);
            }
        }
        int steps=0;
        vector <int> ans;
        while(!even.empty()||!odd.empty()){
            steps++;
            if(steps&1){
                if(odd.size()>0){
                    auto it=*(odd.begin());
                    odd.erase(it);
                    swap(arr[it],arr[it+1]);
                    if(it>1){
                        if(arr[it-1]>arr[it])even.insert(it-1);
                        else if(even.count(it-1))even.erase(it-1);
                    }
                    if(it<n-1){
                        if(arr[it+1]>arr[it+2])even.insert(it+1);
                        else if(even.count(it+1))even.erase(it+1);
                    }
                    ans.push_back(it);
                }
                else {
                    auto it=*(even.begin());
                    even.erase(it);
                    swap(arr[it],arr[it+1]);
                    if(it>2){
                        ans.push_back(1);
                        ans.push_back(it);
                        ans.push_back(1);
                    }
                    else {
                        if(n>=6){
                            ans.push_back(5);
                            ans.push_back(2);
                            ans.push_back(5);
                        }
                        else {
                            ans.push_back(1);
                            ans.push_back(2);
                            ans.push_back(1);
                            ans.push_back(2);
                            ans.push_back(1);
                        }
                    }
                    if(it>1){
                        if(arr[it-1]>arr[it])odd.insert(it-1);
                        else if(odd.count(it-1))odd.erase(it-1);
                    }
                    if(it<n-1){
                        if(arr[it+1]>arr[it+2])odd.insert(it+1);
                        else if(odd.count(it+1))odd.erase(it+1);
                    }
                }
            }
            else {
                if(even.size()>0){
                    auto it=*(even.begin());
                    even.erase(it);
                    swap(arr[it],arr[it+1]);
                    if(it>1){
                        if(arr[it-1]>arr[it])odd.insert(it-1);
                        else if(odd.count(it-1))odd.erase(it-1);
                    }
                    if(it<n-1){
                        if(arr[it+1]>arr[it+2])odd.insert(it+1);
                        else if(odd.count(it+1))odd.erase(it+1);
                    }
                    ans.push_back(it);
                }
                else {
                    auto it=*(odd.begin());
                    odd.erase(it);
                    swap(arr[it],arr[it+1]);
                    if(it>3){
                        ans.push_back(2);
                        ans.push_back(it);
                        ans.push_back(2);
                    }
                    else {
                        if(n>=7){
                            ans.push_back(6);
                            ans.push_back(it);
                            ans.push_back(6);
                        }
                        else {
                            ans.push_back(2);
                            ans.push_back(it);
                            ans.push_back(2);
                            ans.push_back(it);
                            ans.push_back(2);
                        }
                    }
                    if(it>1){
                        if(arr[it-1]>arr[it])even.insert(it-1);
                        else if(even.count(it-1))even.erase(it-1);
                    }
                    if(it<n-1){
                        if(arr[it+1]>arr[it+2])even.insert(it+1);
                        else if(even.count(it+1))even.erase(it+1);
                    }
                }
            }
        }
        cout<<ans.size()<<endl;
        for(auto it:ans)cout<<it<<" ";
        cout<<endl;
    }
    return 0;
}

提出情報

提出日時
問題 C - Odd Even Sort
ユーザ sudipandatta
言語 C++ (GCC 9.2.1)
得点 0
コード長 4920 Byte
結果 WA
実行時間 31 ms
メモリ 3852 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 1
AC × 46
WA × 1
セット名 テストケース
Sample sample_01.txt
All hand_01.txt, hand_02.txt, max_01.txt, max_02.txt, max_03.txt, max_04.txt, max_05.txt, max_06.txt, max_07.txt, max_08.txt, max_09.txt, max_10.txt, max_11.txt, max_12.txt, max_13.txt, max_14.txt, max_15.txt, max_16.txt, max_17.txt, max_18.txt, max_19.txt, max_20.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 31 ms 3784 KiB
hand_02.txt AC 27 ms 3688 KiB
max_01.txt AC 16 ms 3628 KiB
max_02.txt AC 21 ms 3620 KiB
max_03.txt AC 16 ms 3672 KiB
max_04.txt AC 16 ms 3576 KiB
max_05.txt AC 14 ms 3628 KiB
max_06.txt AC 13 ms 3576 KiB
max_07.txt AC 14 ms 3696 KiB
max_08.txt AC 15 ms 3648 KiB
max_09.txt AC 14 ms 3688 KiB
max_10.txt AC 15 ms 3632 KiB
max_11.txt AC 15 ms 3520 KiB
max_12.txt AC 15 ms 3692 KiB
max_13.txt AC 16 ms 3604 KiB
max_14.txt AC 20 ms 3684 KiB
max_15.txt AC 14 ms 3852 KiB
max_16.txt AC 15 ms 3668 KiB
max_17.txt AC 17 ms 3668 KiB
max_18.txt AC 15 ms 3780 KiB
max_19.txt AC 15 ms 3580 KiB
max_20.txt AC 20 ms 3572 KiB
random_01.txt AC 12 ms 3616 KiB
random_02.txt AC 14 ms 3680 KiB
random_03.txt AC 12 ms 3572 KiB
random_04.txt AC 9 ms 3612 KiB
random_05.txt AC 18 ms 3516 KiB
random_06.txt AC 11 ms 3692 KiB
random_07.txt AC 11 ms 3672 KiB
random_08.txt AC 9 ms 3684 KiB
random_09.txt AC 11 ms 3648 KiB
random_10.txt AC 11 ms 3572 KiB
random_11.txt AC 10 ms 3620 KiB
random_12.txt AC 11 ms 3640 KiB
random_13.txt AC 10 ms 3676 KiB
random_14.txt AC 9 ms 3692 KiB
random_15.txt AC 9 ms 3676 KiB
random_16.txt AC 9 ms 3596 KiB
random_17.txt AC 6 ms 3612 KiB
random_18.txt AC 6 ms 3612 KiB
random_19.txt AC 8 ms 3680 KiB
random_20.txt AC 7 ms 3560 KiB
sample_01.txt AC 2 ms 3536 KiB
small_01.txt WA 3 ms 3432 KiB
small_02.txt AC 3 ms 3524 KiB
small_03.txt AC 2 ms 3480 KiB
small_04.txt AC 3 ms 3552 KiB