oj.uz

Submission #63967

# Submission time Handle Problem Language Result Execution time Memory
63967 2018-08-03T07:50:56 Z 강태규(#1867) Ranklist Sorting (BOI07_sorting) C++11
10 / 100
 1000 ms 496 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e9;
int n, mn;
vector<pii> ans;

int pro(vector<int> v, int i, int cost, int ch = 0) {
    if (i < 0) {
        for (int i = 1; i < n; ++i) {
            if (v[i - 1] > v[i]) return inf;
        }
        if (ch && cost == mn) return -1;
        return cost;
    }
    int ret = pro(v, i - 1, cost, ch);
    if (ret == -1) return -1;
    int pi;
    for (int j = 0; j < n; ++j) if (v[j] == i) pi = j;
    for (int j = pi; j > 0; --j) swap(v[j - 1], v[j]);
    for (int j = 0; j < n; ++j) {
        if (j) swap(v[j - 1], v[j]);
        ret = min(ret, pro(v, i - 1, cost + pi + j + 2, ch));
        if (ret == -1) {
            ans.emplace_back(pi + 1, j + 1);
            return -1;
        }
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    if (n > 10) return 0;
    vector<int> s;
    int cp[10];
    for (int i = 0; i < n; ++i) {
        scanf("%d", cp + i);
        s.push_back(cp[i]);
    }
    sort(cp, cp + n);
    for (int &i : s) i = n - 1 - (lower_bound(cp, cp + n, i) - cp);
    
    mn = pro(s, n - 1, 0);
    pro(s, n - 1, 0, 1);
    
    printf("%d\n", (int)ans.size());
    for (int i = ans.size(); i--; ) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
    
	return 0;
}

Compilation message

sorting.cpp: In function 'int main()':
sorting.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sorting.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", cp + i);
         ~~~~~^~~~~~~~~~~~~~
sorting.cpp: In function 'int pro(std::vector<int>, int, int, int)':
sorting.cpp:35:9: warning: 'pi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int pi;
         ^~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 376 KB Output is correct
2 Execution timed out 1086 ms 488 KB Time limit exceeded
3 Execution timed out 1083 ms 488 KB Time limit exceeded
4 Incorrect 2 ms 496 KB Unexpected end of file - int32 expected
5 Incorrect 2 ms 496 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 496 KB Unexpected end of file - int32 expected
7 Incorrect 3 ms 496 KB Unexpected end of file - int32 expected
8 Incorrect 2 ms 496 KB Unexpected end of file - int32 expected
9 Incorrect 3 ms 496 KB Unexpected end of file - int32 expected
10 Incorrect 3 ms 496 KB Unexpected end of file - int32 expected