oj.uz

Submission #422505

# Submission time Handle Problem Language Result Execution time Memory
422505 2021-06-10T07:40:33 Z 반딧불(#7601) Ranklist Sorting (BOI07_sorting) C++17
30 / 100
 1000 ms 204 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void renumber(int n, int *a){
    vector<int> vec(a+1, a+n+1);
    sort(vec.begin(), vec.end());
    for(int i=1; i<=n; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        a[i] = n - 1 - a[i];
    }
}


int n;
int arr[1002];
int ans = INT_MAX;
vector<pair<int, int> > ansVec;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    renumber(n, arr);

    for(int d=0; d<(1<<n); d++){
        vector<int> vec (arr+1, arr+n+1);
        int tans = 0;
        vector<pair<int, int> > tVec;

        /// check if this is valid
        vector<int> selectList;
        bool valid = 1;
        for(int i=0; i<n; i++){
            if((d>>vec[i])%2 == 0) selectList.push_back(vec[i]);
        }
        for(int i=0; i<(int)selectList.size()-1; i++){
            if(selectList[i] > selectList[i+1]) valid = 0;
        }
        if(!valid) continue;

        vector<bool> chk(n);

        for(int ch=0; ch<n; ch++){
            int i = arr[ch+1];
            if((d>>i)%2 == 0) continue;
            vector<pair<int, int> > dest;
            dest.push_back(make_pair(-100, 0));
            for(int j=0; j<n; j++){
                if((d>>vec[j])%2 == 0 || chk[vec[j]]){
//                    printf("%d %d %d\n", i, j, vec[j]);
                    dest.push_back(make_pair(vec[j], j));
                }
            }
            chk[i] = 1;
            dest.push_back(make_pair(100000, n));
            sort(dest.begin(), dest.end());

            auto it = lower_bound(dest.begin(), dest.end(), make_pair(i, 0));
            int now = find(vec.begin(), vec.end(), i) - vec.begin();
            if(prev(it)->second <= now && now <= it->second) continue;

            int goal;
            goal = prev(it)->second;
            if(goal < now) goal++;
            assert(0 <= goal && goal < n);
            tans += (now+1) + (goal+1);
            tVec.push_back(make_pair(now+1, goal+1));

            if(goal < now){
                while(now > goal) swap(vec[now], vec[now-1]), now--;
            }
            else{
                while(now < goal) swap(vec[now], vec[now+1]), now++;
            }
        }
        if(tans < ans){
            ans = tans;
            ansVec = tVec;
        }
    }

    printf("%d\n", (int)ansVec.size());
    for(auto x: ansVec){
        printf("%d %d\n", x.first, x.second);
    }
}

Compilation message

sorting.cpp: In function 'int main()':
sorting.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sorting.cpp:24:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 129 ms 204 KB not sorted
5 Incorrect 1 ms 204 KB not sorted
6 Incorrect 1 ms 204 KB not sorted
7 Execution timed out 1087 ms 204 KB Time limit exceeded
8 Incorrect 1 ms 204 KB not sorted
9 Incorrect 1 ms 204 KB not sorted
10 Incorrect 2 ms 204 KB not sorted