oj.uz

Submission #989575

# Submission time Handle Problem Language Result Execution time Memory
989575 2024-05-28T10:49:32 Z crafticat Sorting (IOI15_sorting) C++17
54 / 100
 3 ms 1116 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> 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;
    }
    int countSort = 0;
    for (int i = 0; i < n; ++i) {
        if (pos[i] != i) {
            notSorted[i] = true;
            countSort++;
        }
    }
    int iter = 0;
    for (int i = 0; i < m; ++i) {
        int j = i % n;
        if (!notSorted[pos[j]]) continue;
        swap(orgPosTo[x[iter]], orgPosTo[y[iter]]);
        orgPos[orgPosTo[x[iter]]] = x[iter];
        orgPos[orgPosTo[y[iter]]] = y[iter];

        int target = pos[j];

        if (notSorted[target]) {
            notSorted[target] = false;
            countSort--;
        }

        swap(pos[target],pos[j]);
        if (pos[j] == j) {
            if (notSorted[j]) {
                notSorted[j] = false;
                countSort--;
            }
        }
        ans.emplace_back(orgPos[j],orgPos[target]);
        iter++;
    }
    for (int i = ans.size(); i < m; ++i) {
        int j = i % n;
        swap(orgPosTo[x[iter]], orgPosTo[y[iter]]);
        orgPos[orgPosTo[x[iter]]] = x[iter];
        orgPos[orgPosTo[y[iter]]] = y[iter];

        int target = pos[j];

        if (notSorted[target]) {
            notSorted[target] = false;
            countSort--;
        }

        swap(pos[target],pos[j]);
        if (pos[j] == j) {
            if (notSorted[j]) {
                notSorted[j] = false;
                countSort--;
            }
        }
        ans.emplace_back(orgPos[j],orgPos[target]);
        iter++;
    }
    if (countSort > 0) return {};
    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:72:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   72 |     for (int i = ans.size(); i < m; ++i) {
      |                  ~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:134: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]
  134 |         for (int j = 0; j < v.size(); ++j) {
      |                         ~~^~~~~~~~~~
sorting.cpp:137: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]
  137 |         for (int j = 0; j < v.size(); ++j) {
      |                         ~~^~~~~~~~~~
sorting.cpp:140:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  140 |         return v.size();
      |                ~~~~~~^~
sorting.cpp:132:21: warning: control reaches end of non-void function [-Wreturn-type]
  132 |     auto v = solve(l);
      |                     ^

Subtask #1
8.0 / 8.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 0 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
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.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 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.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 0 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
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 856 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 856 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1116 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1116 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -