Submission #778322

#TimeUsernameProblemLanguageResultExecution timeMemory
778322danikoynovSorting (IOI15_sorting)C++14
20 / 100
9 ms340 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int n, arr[maxn], used[maxn]; vector < pair < int, int > > edges; int count_steps() { for (int i = 0; i < n; i ++) used[i] = 0; int ans = 0; for (int i = 0; i < n; i ++) { if (used[i]) continue; int v = arr[i], cnt = 0; while(v != i) { used[v] = 1; cnt ++; v = arr[v]; } used[v] = 1; cnt ++; ans = ans + (cnt - 1); } return ans; } void build_edges() { for (int i = 0; i < n; i ++) used[i] = 0; for (int i = 0; i < n; i ++) { if (used[i]) continue; vector < int > ord; int v = arr[i]; while(v != i) { ord.push_back(v); used[v] = 1; v = arr[v]; } ord.push_back(i); used[i] = 1; for (int i = 0; i < ord.size() - 1; i ++) edges.push_back({arr[ord[i]], arr[ord[i + 1]]}); } } int pos[maxn]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; bool sorted = true; for (int i = 0; i < N; i ++) if (S[i] != i) sorted = false; if (sorted) return 0; for (int i = 0; i < N; i ++) arr[i] = S[i]; int pivot = -1; for (int i = 0; i < N; i ++) { swap(arr[X[i]], arr[Y[i]]); int steps = count_steps(); /**cout << "--------------" << endl; for (int j = 0; j < N; j ++) cout << arr[j] << " "; cout << endl; cout << steps << endl;*/ if (steps <= i + 1) { pivot = i; break; } } ///cout << pivot << endl; ///exit(0); build_edges(); for (int i = 0; i < n; i ++) pos[S[i]] = i; for (int i = 0; i < edges.size(); i ++) { ///cout << edges[i].first << " : " << edges[i].second << endl; P[i] = pos[edges[i].first]; Q[i] = pos[edges[i].second]; swap(pos[edges[i].first], pos[edges[i].second]); int id1 = 0, id2 = 0; while(pos[id1] != X[i]) id1 ++; while(pos[id2] != Y[i]) id2 ++; ///cout << id1 << " : " << id2 << endl; swap(pos[id1], pos[id2]); ///swap(pos[X[i]], pos[Y[i]]); } for (int i = edges.size(); i <= pivot; i ++) P[i] = Q[i] = 0; return pivot + 1; }

Compilation message (stderr)

sorting.cpp: In function 'void build_edges()':
sorting.cpp:51:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
   51 |         for (int i = 0; i < ord.size() - 1; i ++)
      |                  ^
sorting.cpp:36:14: note: shadowed declaration is here
   36 |     for (int i = 0; i < n; i ++)
      |              ^
sorting.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < ord.size() - 1; i ++)
      |                         ~~^~~~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:91: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]
   91 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
sorting.cpp:106:28: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  106 |     for (int i = edges.size(); i <= pivot; i ++)
      |                  ~~~~~~~~~~^~
sorting.cpp:57:39: warning: unused parameter 'M' [-Wunused-parameter]
   57 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                   ~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...