結果
問題 | No.397 NO MORE KADOMATSU |
ユーザー | moyashi_senpai |
提出日時 | 2016-07-15 23:18:36 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,044 bytes |
コンパイル時間 | 529 ms |
コンパイル使用メモリ | 74,576 KB |
実行使用メモリ | 35,952 KB |
最終ジャッジ日時 | 2023-09-24 00:17:13 |
合計ジャッジ時間 | 6,996 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
ソースコード
#include <iostream> #include <cstdio> #include <vector> #include <cmath> #include <cstring> #include <numeric> #include <algorithm> #include <functional> #include <array> #include <map> using namespace std; #define Getsign(n) ((n > 0) - (n < 0)) typedef vector<int> Ivec; typedef pair<int, int> Pos; vector <pair<int, int>> history; long long int tesu = 0; /* 配列の要素を交換する */ void Swap(int x [], int i, int j) { int temp; temp = x[i]; x[i] = x[j]; x[j] = temp; history.push_back({i,j}); tesu++; } /* クイックソートを行う */ void QSort(int x [], int left, int right) { int i, j; int pivot; i = left; /* ソートする配列の一番小さい要素の添字 */ j = right; /* ソートする配列の一番大きい要素の添字 */ pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */ while (1) { /* 無限ループ */ while (x[i] < pivot) /* pivot より大きい値が */ i++; /* 出るまで i を増加させる */ while (pivot < x[j]) /* pivot より小さい値が */ j--; /* 出るまで j を減少させる */ if (i >= j) /* i >= j なら */ break; /* 無限ループから抜ける */ Swap(x, i, j); /* x[i] と x[j]を交換 */ i++; /* 次のデータ */ j--; } if (left < i - 1) /* 基準値の左に 2 以上要素があれば */ QSort(x, left, i - 1); /* 左の配列を Q ソートする */ if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */ QSort(x, j + 1, right); /* 右の配列を Q ソートする */ } int main() { int n, a[100]; scanf("%d", &n); for (int i = 0; n > i; i++) { scanf("%d", &a[i]); } QSort(a, 0, n-1); printf("%d\n", tesu); for (int i = 0; tesu > i; i++) { printf("%d %d\n", history[i].first, history[i].second); } scanf("%*d"); fflush(stdout); return 0; }