oj.uz

Submission #989586

# Submission time Handle Problem Language Result Execution time Memory
989586 2024-05-28T11:05:31 Z crafticat Sorting (IOI15_sorting) C++17
36 / 100
 1000 ms 20564 KB 
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

vector<int> x, y;
vector<int> initPos;
int n;

bool check(vector<pii> test) {
    vector<int> pos = initPos;
    for (int i = 0; i < test.size(); ++i) {
        swap(pos[x[i]],pos[y[i]]);
        swap(pos[test[i].first],pos[test[i].second]);
    }
    for (int i = 0; i < n; ++i) {
        if (pos[i] != i)
            return false;
    }
    return true;
}

vector<pii> solve(int m) {
    vector<int> pos = initPos;
    vector<int> posPoint = initPos;
    vector<int> orgPosTo(n), orgPos(n);
    vector<bool> notSorted(n);
    vector<pii> ans;
    for (int i = 0; i < n; ++i) {
        orgPosTo[i] = i;
    }
    for (int i = 0;i < m;i++) {
        swap(pos[x[i]],pos[y[i]]);
    }
    for (int i = m - 1; i >=0 ; --i) {
        swap(orgPosTo[x[i]],orgPosTo[y[i]]);
    }
    for (int i = 0; i < n; ++i) {
        orgPos[orgPosTo[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        if (pos[i] != i) notSorted[i] = true;
        posPoint[pos[i]] = i;
    }
    for (int k = 0; k < n; ++k) {
        posPoint[pos[k]] = k;
    }
    int iter = 0;
    for (int i = 0; iter < min(n,m) && i < n; ++i) {
        int j = posPoint[i % n];
        if (!notSorted[pos[i % n]]) continue;
        swap(orgPosTo[x[iter]],orgPosTo[y[iter]]);
        orgPos[orgPosTo[x[iter]]] = x[iter];
        orgPos[orgPosTo[y[iter]]] = y[iter];

        int target = pos[j];
        notSorted[target] = false;

        swap(pos[target],pos[j]);
        for (int k = 0; k < n; ++k) {
            posPoint[pos[k]] = k;
        }
        if (pos[j] == j)
            notSorted[j] = false;
        ans.emplace_back(orgPos[j],orgPos[target]);
        iter++;
    }
    for (int i = 0; i < n; ++i) {
        if (notSorted[i]) {
            if (ans.size() < m - 1)
                exit(4);
            return {};
        }
    }
    for (int i = ans.size(); i < m; ++i) {
        ans.emplace_back(0,0);
    }
    if (!check(ans))
        exit(5);
    return ans;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    x.resize(M);
    y.resize(M);
    initPos.resize(n);

    for (int i = 0; i < M; ++i) {
        x[i] = X[i];
    }
    for (int i = 0; i < M; ++i) {
        y[i] = Y[i];
    }
    for (int i = 0; i < n; ++i) {
        initPos[i] = S[i];
    }

    bool stopIm = true;
    for (int i = 0; i < n; ++i) {
        if (initPos[i] != i) stopIm = false;
    }
    if (stopIm) return {};

    int l = 0, r = M;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (solve(mid).empty()) {
            l = mid + 1;
        } else
            r = mid;
    }

    auto v = solve(l);
    if (!v.empty()) {
        for (int j = 0; j < v.size(); ++j) {
            P[j] = v[j].first;
        }
        for (int j = 0; j < v.size(); ++j) {
            Q[j] = v[j].second;
        }
        return v.size();
    }
}

#if DEBUG
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int x; cin >> x;
    return x;
}


int main()
{
    _inputFile = fopen("sorting.in", "rb");
    _outputFile = fopen("sorting.out", "w");
    int N, M;
    N = _readInt();
    int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
    for (int i = 0; i < N; ++i)
        S[i] = _readInt();
    M = _readInt();
    int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
    for (int i = 0; i < M; ++i) {
        X[i] = _readInt();
        Y[i] = _readInt();
    }
    int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
    int ans = findSwapPairs(N, S, M, X, Y, P, Q);
    cout << ans << endl;
    for (int i = 0; i < ans; ++i)
        cout << P[i] << " " << Q[i] << endl;
    return 0;
}
#endif

Compilation message

sorting.cpp: In function 'bool check(std::vector<std::pair<int, int> >)':
sorting.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < test.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
sorting.cpp: In function 'std::vector<std::pair<int, int> > solve(int)':
sorting.cpp:70:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             if (ans.size() < m - 1)
      |                 ~~~~~~~~~~~^~~~~~~
sorting.cpp:75:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |     for (int i = ans.size(); i < m; ++i) {
      |                  ~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int j = 0; j < v.size(); ++j) {
      |                         ~~^~~~~~~~~~
sorting.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j = 0; j < v.size(); ++j) {
      |                         ~~^~~~~~~~~~
sorting.cpp:122:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  122 |         return v.size();
      |                ~~~~~~^~
sorting.cpp:114:21: warning: control reaches end of non-void function [-Wreturn-type]
  114 |     auto v = solve(l);
      |                     ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Runtime error 0 ms 344 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 604 KB Output is correct
2 Correct 42 ms 856 KB Output is correct
3 Correct 33 ms 672 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 12 ms 664 KB Output is correct
7 Correct 28 ms 656 KB Output is correct
8 Correct 67 ms 668 KB Output is correct
9 Correct 43 ms 600 KB Output is correct
10 Correct 46 ms 600 KB Output is correct
11 Correct 36 ms 704 KB Output is correct
12 Correct 26 ms 604 KB Output is correct
13 Correct 40 ms 700 KB Output is correct
14 Correct 1 ms 600 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 604 KB Output is correct
2 Correct 42 ms 856 KB Output is correct
3 Correct 33 ms 672 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 12 ms 664 KB Output is correct
7 Correct 28 ms 656 KB Output is correct
8 Correct 67 ms 668 KB Output is correct
9 Correct 43 ms 600 KB Output is correct
10 Correct 46 ms 600 KB Output is correct
11 Correct 36 ms 704 KB Output is correct
12 Correct 26 ms 604 KB Output is correct
13 Correct 40 ms 700 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Execution timed out 1057 ms 20564 KB Time limit exceeded
16 Halted 0 ms 0 KB -