oj.uz

답안 #1018570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018570 2024-07-10T06:58:03 Z huutuan 정렬하기 (IOI15_sorting) C++14
74 / 100
 1000 ms 23380 KB 
#include "sorting.h"

#include <bits/stdc++.h>

using namespace std;

int a[200010], pos[200010], s[200010];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
   if (is_sorted(S, S+N)) return 0;
   for (int _=0; _<M; ++_){
      for (int i=0; i<N; ++i) s[i]=S[i];
      for (int i=0; i<N; ++i) pos[s[i]]=i;
      iota(a, a+N, 0);
      for (int i=_; i>=0; --i) swap(a[X[i]], a[Y[i]]);
      set<int> st;
      for (int i=0; i<N; ++i) if (a[i]!=s[i]) st.insert(i);
      for (int i=0; i<=_; ++i){
         P[i]=Q[i]=0;
         swap(a[X[i]], a[Y[i]]);
         swap(s[X[i]], s[Y[i]]);
         pos[s[X[i]]]=X[i];
         pos[s[Y[i]]]=Y[i];
         st.erase(X[i]); st.erase(Y[i]);
         if (a[X[i]]!=s[X[i]]) st.insert(X[i]);
         if (a[Y[i]]!=s[Y[i]]) st.insert(Y[i]);
         // if (is_sorted(s, s+N)){
         //    return i+1;
         // }
         if (st.size()){
            int j=*st.begin(); st.erase(st.begin());
            int k=pos[a[j]];
            P[i]=j, Q[i]=k;
         }
         swap(s[P[i]], s[Q[i]]);
         pos[s[P[i]]]=P[i];
         pos[s[Q[i]]]=Q[i];
         st.erase(P[i]); st.erase(Q[i]);
         if (a[P[i]]!=s[P[i]]) st.insert(P[i]);
         if (a[Q[i]]!=s[Q[i]]) st.insert(Q[i]);
         // if (is_sorted(s, s+N)){
         //    return i+1;
         // }
      }
      if (is_sorted(s, s+N)) return _+1;
   }
   return -1;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 2404 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 29 ms 2396 KB Output is correct
22 Correct 29 ms 2392 KB Output is correct
23 Correct 35 ms 2396 KB Output is correct
24 Correct 26 ms 2392 KB Output is correct
25 Correct 6 ms 2648 KB Output is correct
26 Correct 12 ms 2396 KB Output is correct
27 Correct 34 ms 2616 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 622 ms 2636 KB Output is correct
2 Correct 659 ms 2652 KB Output is correct
3 Correct 805 ms 2648 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 28 ms 2644 KB Output is correct
7 Correct 224 ms 2648 KB Output is correct
8 Correct 791 ms 2648 KB Output is correct
9 Correct 929 ms 2940 KB Output is correct
10 Correct 836 ms 2684 KB Output is correct
11 Correct 668 ms 2652 KB Output is correct
12 Correct 230 ms 2652 KB Output is correct
13 Correct 718 ms 2752 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 622 ms 2636 KB Output is correct
2 Correct 659 ms 2652 KB Output is correct
3 Correct 805 ms 2648 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 28 ms 2644 KB Output is correct
7 Correct 224 ms 2648 KB Output is correct
8 Correct 791 ms 2648 KB Output is correct
9 Correct 929 ms 2940 KB Output is correct
10 Correct 836 ms 2684 KB Output is correct
11 Correct 668 ms 2652 KB Output is correct
12 Correct 230 ms 2652 KB Output is correct
13 Correct 718 ms 2752 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Execution timed out 1052 ms 23380 KB Time limit exceeded
16 Halted 0 ms 0 KB -