Submission #294034

# Submission time Handle Problem Language Result Execution time Memory
294034 2020-09-08T14:35:43 Z arayi Sorting (IOI15_sorting) C++17
0 / 100
4 ms 896 KB
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;

const int N = 2e5 + 30;

int n, m;
int a[N], ind[N], b[N], x[N], y[N];
int col[N];
bool stg(int m)
{
    for (int i = 0; i < m; i++)
    {
        if(x[i] == y[i]) continue;
        col[x[i]]++, col[y[i]]++;
    }
    queue <int> q;
    for (int i = 0; i < n; i++)
        if(!col[i]) q.push(i);
    for (int i = 0; i < m; i++)
    {
        swap(a[x[i]], a[y[i]]);
        if(x[i] != y[i])
        {
            col[x[i]]--, col[y[i]]--;
            if(!col[x[i]]) q.push(x[i]);
            if(!col[y[i]]) q.push(y[i]);
            ind[a[x[i]]] = x[i];
            ind[a[y[i]]] = y[i];
        }
        while(!q.empty() && q.front() == a[q.front()]) q.pop();
        if(q.empty()) continue;
        else
        {
            int i1 = q.front();
            //cout << i1 << endl;
            swap(a[i1], a[ind[i1]]);
            ind[a[i1]] = i1;
            ind[a[ind[i1]]] = ind[i1];
            q.pop();
        }
    }
    for (int i = 0; i < n; i++) if(a[i] != i) return false;
    return true;

}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N;
    for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i;
    for (int i = 0; i < M; i++) x[i] = X[i], y[i] = Y[i];
    int l = 0, r = M, ans = M;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i, col[i] = 0;
        if(stg(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i, col[i] = 0;
    m = ans;
    for (int i = 0; i < m; i++)
    {
        if(x[i] == y[i]) continue;
        col[x[i]]++, col[y[i]]++;
    }
    queue <int> q;
    for (int i = 0; i < n; i++)
        if(!col[i]) q.push(i);
    for (int i = 0; i < m; i++)
    {
        swap(a[x[i]], a[y[i]]);
        if(x[i] != y[i])
        {
            col[x[i]]--, col[y[i]]--;
            if(!col[x[i]]) q.push(x[i]);
            if(!col[y[i]]) q.push(y[i]);
            ind[a[x[i]]] = x[i];
            ind[a[y[i]]] = y[i];
        }
        while(!q.empty() && q.front() == a[q.front()]) q.pop();
        if(q.empty()) P[i] = Q[i] = 0;
        else
        {
            int i1 = q.front();
            //cout << i1 << endl;
            P[i] = i1;
            Q[i] = ind[i1];
            swap(a[P[i]], a[Q[i]]);
            ind[a[P[i]]] = P[i];
            ind[a[Q[i]]] = Q[i];
            q.pop();
        }
    }
    while(!q.empty() && q.front() == a[q.front()]) q.pop();
    if(!q.empty()) assert(0);
    return m;
}


Compilation message

sorting.cpp: In function 'bool stg(int)':
sorting.cpp:10:15: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   10 | bool stg(int m)
      |               ^
sorting.cpp:7:8: note: shadowed declaration is here
    7 | int n, m;
      |        ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:47:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   47 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                                                            ^
sorting.cpp:5:11: note: shadowed declaration is here
    5 | const int N = 2e5 + 30;
      |           ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -