oj.uz

Submission #712951

# Submission time Handle Problem Language Result Execution time Memory
712951 2023-03-20T14:48:33 Z Nhoksocqt1 Sorting (IOI15_sorting) C++17
100 / 100
 914 ms 136500 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
#define round asfhuqfuqwhuqwer
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;
const int MAX_LOG = 20;

ii round[3 * MAXN];
int val[MAXN], h[6 * MAXN], P[6 * MAXN][MAX_LOG], Pn[6 * MAXN], lastOf[MAXN], lastNow[6 * MAXN];
int lastIdx[MAXN], pos[MAXN], tmp[MAXN], nArr, numRound;

#ifdef Nhoksocqt1

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[]);
int _S[MAXN], _X[3 * MAXN], _Y[3 * MAXN], _P[3 * MAXN], _Q[3 * MAXN];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("SORTING.inp", "r", stdin);
    freopen("SORTING.out", "w", stdout);

    int _N, _M;
    cin >> _N;
    for (int i = 0; i < _N; ++i)
        cin >> _S[i];

    //for (int i = 0; i < _N; ++i) _S[i] = i; shuffle(_S, _S + _N, rng); for (int i = 0; i < _N; ++i) cout << _S[i] << " \n"[i + 1 == _N];

    cin >> _M; //_M = 2e5;
    for (int i = 0; i < _M; ++i) {
        cin >> _X[i];
        //_X[i] = Random(0, _N - 1); cout << _X[i] << " \n"[i + 1 == _M];
    }

    for (int i = 0; i < _M; ++i) {
        cin >> _Y[i];
        //_Y[i] = Random(0, _N - 1); cout << _Y[i] << " \n"[i + 1 == _M];
    }

    int ans = findSwapPairs(_N, _S, _M, _X, _Y, _P, _Q);
    cout << ans << '\n';
    for (int it = 0; it < ans; ++it)
        cout << _P[it] << ' ' << _Q[it] << '\n';

    return 0;
}

#endif // Nhoksocqt1

inline int getID(int x) {
    return (x > numRound) ? round[x - numRound].fi : round[x].se;
}

bool check(int nr) {
    for (int i = 1; i <= nArr; ++i) {
        tmp[i] = val[i];
        pos[val[i]] = i;
    }

    for (int i = 1; i <= numRound; ++i) {
        lastNow[i] = (i > nr ? lastNow[Pn[i]] : i);
        lastNow[i + numRound] = (i > nr ? lastNow[Pn[i + numRound]] : i + numRound);
    }

    for (int i = 1; i <= numRound; ++i) {
        lastNow[i] = (P[lastNow[i]][0] ? lastNow[P[lastNow[i]][0]] : lastNow[i]);
        lastNow[i + numRound] = (P[lastNow[i + numRound]][0] ? lastNow[P[lastNow[i + numRound]][0]] : lastNow[i + numRound]);
    }

    int cntNow(1);
    for (int i = 1; i <= nArr; ++i) {
        int from(lastNow[lastOf[i]]);
        bool checkCond(from > 0);
        if(checkCond && tmp[getID(from)] == i || !checkCond && tmp[i] == i)
            continue;

        if(cntNow > nr)
            return false;

        int x(pos[i]), y = (checkCond ? getID(from) : i);
        swap(pos[tmp[x]], pos[tmp[y]]);
        swap(tmp[x], tmp[y]);

        //cout << nr << ": " << x << ' ' << y << ' ' << from << '\n';
        ++cntNow;
    }

    return true;
}

bool traceAnswer(int nr, int _P[], int _Q[]) {
    for (int i = 1; i <= nArr; ++i) {
        tmp[i] = val[i];
        pos[val[i]] = i;
    }

    swap(pos[tmp[round[1].fi]], pos[tmp[round[1].se]]);
    swap(tmp[round[1].fi], tmp[round[1].se]);
    for (int i = 1; i <= numRound; ++i) {
        lastNow[i] = (i > nr ? lastNow[Pn[i]] : i);
        lastNow[i + numRound] = (i > nr ? lastNow[Pn[i + numRound]] : i + numRound);
    }

    int cntNow(1);
    for (int i = 1; i <= nArr; ++i) {
        int from(lastNow[lastOf[i]]);
        if(from > 0 && (from <= numRound && from > cntNow || from - numRound > cntNow)) {
            //cout << h[from] << ' ' << 31 - __builtin_clz(h[from]) << '\n';
            for (int j = 31 - __builtin_clz(h[from]); j >= 0; --j) {
                int now(P[from][j]);
                //cout << now << ' ' << cntNow << '.';
                if(now <= numRound && now > cntNow || now - numRound > cntNow)
                    from = now;
            }
        }

        //cout << nr << ' ' << i << ' ' << tmp[getID(from)] << ' ' << lastOf[i] << ' ' << from << ' ' << getID(from) << '\n';
        bool checkCond = (from <= numRound && from > cntNow || from - numRound > cntNow);
        if(checkCond && tmp[getID(from)] == i || !checkCond && tmp[i] == i)
            continue;

        if(cntNow > nr)
            return false;

        int x(pos[i]), y = (checkCond ? getID(from) : i);

        _P[cntNow - 1] = x - 1, _Q[cntNow - 1] = y - 1;
        swap(pos[tmp[x]], pos[tmp[y]]);
        swap(tmp[x], tmp[y]);

        //cout << '.' << x << ' ' << y << '\n';
        if(++cntNow <= nr) {
            swap(pos[tmp[round[cntNow].fi]], pos[tmp[round[cntNow].se]]);
            swap(tmp[round[cntNow].fi], tmp[round[cntNow].se]);
        }
    }

    return true;
}

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[]) {
    nArr = _N, numRound = _M;

    bool check0(1);
    for (int i = 1; i <= nArr; ++i) {
        val[i] = _S[i - 1] + 1;
        check0 &= (val[i] == i);
    }

    if(check0)
        return 0;

    for (int i = 1; i <= numRound; ++i) {
        round[i] = {_X[i - 1] + 1, _Y[i - 1] + 1};

        P[i][0] = lastIdx[round[i].se];
        P[i + numRound][0] = lastIdx[round[i].fi];
        h[i + numRound] = 1 + h[P[i + numRound][0]];
        h[i] = 1 + h[P[i][0]];

        Pn[i] = lastIdx[round[i].fi];
        Pn[i + numRound] = lastIdx[round[i].se];
        lastIdx[round[i].se] = i + numRound;
        lastIdx[round[i].fi] = i;
        lastOf[round[i].fi] = i;
        lastOf[round[i].se] = i + numRound;
    }

    for (int j = 1; (1 << j) <= numRound; ++j) {
        for (int i = 1; i <= 2 * numRound; ++i)
            P[i][j] = P[P[i][j - 1]][j - 1];
    }

    int l(1), r(min(nArr, numRound - 1)), answer(r + 1);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            answer = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    for (int i = 0; i < numRound; ++i)
        _P[i] = _Q[i] = 0;

    traceAnswer(answer, _P, _Q);
    return answer;
}

Compilation message

sorting.cpp: In function 'bool check(int)':
sorting.cpp:93:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 |         if(checkCond && tmp[getID(from)] == i || !checkCond && tmp[i] == i)
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sorting.cpp: In function 'bool traceAnswer(int, int*, int*)':
sorting.cpp:126:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  126 |         if(from > 0 && (from <= numRound && from > cntNow || from - numRound > cntNow)) {
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
sorting.cpp:131:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  131 |                 if(now <= numRound && now > cntNow || now - numRound > cntNow)
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
sorting.cpp:137:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  137 |         bool checkCond = (from <= numRound && from > cntNow || from - numRound > cntNow);
      |                           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
sorting.cpp:138:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  138 |         if(checkCond && tmp[getID(from)] == i || !checkCond && tmp[i] == i)
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 4 ms 3420 KB Output is correct
22 Correct 5 ms 3296 KB Output is correct
23 Correct 6 ms 3412 KB Output is correct
24 Correct 4 ms 3396 KB Output is correct
25 Correct 4 ms 3400 KB Output is correct
26 Correct 5 ms 3388 KB Output is correct
27 Correct 5 ms 3284 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 2 ms 1684 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1620 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 3 ms 1668 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1620 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 2 ms 1684 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1620 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 3 ms 1668 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 2 ms 1620 KB Output is correct
15 Correct 370 ms 114304 KB Output is correct
16 Correct 397 ms 117900 KB Output is correct
17 Correct 809 ms 123976 KB Output is correct
18 Correct 44 ms 12876 KB Output is correct
19 Correct 651 ms 132332 KB Output is correct
20 Correct 698 ms 135340 KB Output is correct
21 Correct 717 ms 135428 KB Output is correct
22 Correct 434 ms 127308 KB Output is correct
23 Correct 426 ms 134920 KB Output is correct
24 Correct 791 ms 133104 KB Output is correct
25 Correct 783 ms 131260 KB Output is correct
26 Correct 591 ms 135560 KB Output is correct
27 Correct 547 ms 132752 KB Output is correct
28 Correct 582 ms 133200 KB Output is correct
29 Correct 694 ms 131952 KB Output is correct
30 Correct 492 ms 133004 KB Output is correct
31 Correct 846 ms 134624 KB Output is correct
32 Correct 417 ms 129476 KB Output is correct
33 Correct 866 ms 132996 KB Output is correct
34 Correct 421 ms 132500 KB Output is correct
35 Correct 648 ms 130284 KB Output is correct
36 Correct 406 ms 131592 KB Output is correct
37 Correct 899 ms 136500 KB Output is correct
38 Correct 888 ms 131232 KB Output is correct
39 Correct 914 ms 132016 KB Output is correct