제출 #1117906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117906		12345678	Xor Sort (eJOI20_xorsort)	C++17	60 / 100	105 ms	16244 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int s, n, vs[nx], a[nx];
vector<pair<int, int>> res;

void solve(int sz)
{
    pair<int, pair<int, int>> mx;
    int cnt=0;
    for (int i=1; i<=n; i++) if (!vs[i]) mx=max(mx, {a[i], {i, ++cnt}});
    vs[mx.second.first]=1;
    //cout<<"debug "<<mx.second.first<<' '<<mx.second.second<<'\n';
    cnt=mx.second.second;
    for (int i=1; i<sz; i++) res.push_back({i, i+1});
    for (int i=cnt; i<sz; i++) res.push_back({i+1, i});
    for (int i=cnt-2; i>=1; i--) res.push_back({i, i+1});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) solve(n-i+1);
    for (int i=n-1; i>=1; i--) res.push_back({i, i+1});
    cout<<res.size()<<'\n';
    for (auto x:res) cout<<x.first<<' '<<x.second<<'\n';
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40