Submission #790057

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
790057	2023-07-22 09:59:09	peteza	Sorting (IOI15_sorting)	C++14	100 / 100	141 ms	16624 KiB

sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int cur[200005], N;
bool vis[200005];
int pos[200005];
int countcompo() {
  for(int j=0;j<=N;j++) vis[j] = 0;
  int cnt = 0;
  for(int i=0;i<N;i++) {
    if(vis[i]) continue;
    vis[i] = 1;
    cnt++;
    int j=i;
    do vis[j=cur[j]] = 1; while(j != i);
  }
  return cnt;
}
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++) cur[i] = S[i];
  memset(P, 0, 4*M); memset(Q, 0, 4 * M);
  if(countcompo() == N) return 0;
  int l=0, r=M;
  while(l <= r) {
    int mid = (l+r) >> 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:22:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   22 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:5:18: note: shadowed declaration is here
    5 | int cur[200005], N;
      |                  ^
sorting.cpp:46:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   46 |    for(int i=0;i<N;i++) {
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:49:10: warning: declaration of 'l' shadows a previous local [-Wshadow]
   49 |      int l = i, j = cur[i];
      |          ^
sorting.cpp:28:6: note: shadowed declaration is here
   28 |  int l=0, r=M;
      |      ^
sorting.cpp:59:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   59 |    for(int i=0;i<N;i++) pos[S[i]] = i;
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26