Submission #774959

#TimeUsernameProblemLanguageResultExecution timeMemory
774959CDuongXor Sort (eJOI20_xorsort)C++17
60 / 100
5 ms984 KiB
/* pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define vi vector<int> #define vii vector<pii> #define isz(x) (int)x.size() using namespace std; const int mxN = 2e5 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int S, n, a[mxN], idx[mxN], maintain[mxN]; void sub2() { } void sub1() { iota(idx + 1, idx + n + 1, 1); iota(maintain + 1, maintain + n + 1, 1); sort(idx + 1, idx + n + 1, [&](int x, int y) { if(a[x] == a[y]) return x < y; return a[x] < a[y]; }); vii op; for(int i = 1; i < n; ++i) op.emplace_back(i, i + 1); for(int i = n; i > 1; --i) { int pos = -1; for(int j = 1; j <= i; ++j) { if(idx[i] == maintain[j]) { pos = j; break; } } if(pos == i) { op.emplace_back(pos - 1, pos); continue; } for(int j = pos + 1; j <= i; ++j) op.emplace_back(j, j - 1); for(int j = max(1, pos - 1); j < i; ++j) op.emplace_back(j, j + 1); for(int j = pos; j < i; ++j) swap(maintain[j], maintain[j + 1]); } cout << isz(op) << "\n"; for(auto tmp : op) cout << tmp.ff << " " << tmp.ss << "\n"; } void solve() { cin >> n >> S; for(int i = 1; i <= n; ++i) cin >> a[i]; if(S == 1) sub1(); else sub2(); } signed main() { #ifndef CDuongg if(fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...