oj.uz

Submission #67945

# Submission time Handle Problem Language Result Execution time Memory
67945 2018-08-15T15:01:40 Z funcsr Sorting (IOI15_sorting) C++17
100 / 100
 440 ms 13756 KB 
#include "sorting.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define _1 first
#define _2 second

int S[200000];
bool used[200000];
vector<pair<int, int> > f(int R, int N, int SS[], int X[], int Y[]) {
  rep(i, N) S[i] = SS[i];
  rep(i, R) swap(S[X[i]], S[Y[i]]);
  rep(i, N) used[i] = false;
  vector<pair<int, int> > ret;
  rep(s, N) if (!used[s]) {
    vector<int> seq;
    int v = s;
    used[v] = true;
    seq.pb(v);
    while (true) {
      v = S[v];
      if (v == s) break;
      assert(!used[v]);
      seq.pb(v);
      used[v] = true;
    }
    for (int i=seq.size()-1; i>0; i--) ret.pb(make_pair(seq[0], seq[i]));
  }
  if (ret.size() > R) return {};
  ret.pb(make_pair(-1, -1)); // dummy
  return ret;
}

int rev[200000];
void swapV(int a, int b) {
  swap(rev[S[a]], rev[S[b]]);
  swap(S[a], S[b]);
}
int findSwapPairs(int N, int SS[], int M, int X[], int Y[], int P[], int Q[]) {
  if (is_sorted(SS, SS+N)) return 0;
  int lo = 0, hi = M;
  while (hi-lo>1) {
    int mid = (lo+hi)/2;
    if (!f(mid, N, SS, X, Y).empty()) hi = mid;
    else lo = mid;
  }
  int R = hi;
  vector<pair<int,int> > swaps = f(R, N, SS, X, Y); swaps.pop_back();
  assert(swaps.size() <= R);
  //cout<<"R="<<R<<": swaps={";for(auto p:swaps)cout<<p._1<<"<->"<<p._2<<",";cout<<"}\n";
  rep(i, N) S[i] = SS[i], rev[SS[i]] = i;
  rep(i, R) {
    swapV(X[i], Y[i]);
    if (i < swaps.size()) P[i] = rev[swaps[i]._1], Q[i] = rev[swaps[i]._2];
    else P[i] = Q[i] = 0;
    swapV(P[i], Q[i]);
  }
  return R;
}

Compilation message

sorting.cpp: In function 'std::vector<std::pair<int, int> > f(int, int, int*, int*, int*)':
sorting.cpp:31:26: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     for (int i=seq.size()-1; i>0; i--) ret.pb(make_pair(seq[0], seq[i]));
                ~~~~~~~~~~^~
sorting.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ret.size() > R) return {};
       ~~~~~~~~~~~^~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from sorting.cpp:5:
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(swaps.size() <= R);
          ~~~~~~~~~~~~~^~~~
sorting.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < swaps.size()) P[i] = rev[swaps[i]._1], Q[i] = rev[swaps[i]._2];
         ~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 3 ms 256 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 4 ms 512 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 293 ms 11904 KB Output is correct
16 Correct 342 ms 12340 KB Output is correct
17 Correct 343 ms 13048 KB Output is correct
18 Correct 38 ms 5368 KB Output is correct
19 Correct 307 ms 11308 KB Output is correct
20 Correct 433 ms 11876 KB Output is correct
21 Correct 334 ms 11864 KB Output is correct
22 Correct 311 ms 13140 KB Output is correct
23 Correct 349 ms 13432 KB Output is correct
24 Correct 334 ms 13144 KB Output is correct
25 Correct 354 ms 13080 KB Output is correct
26 Correct 429 ms 10424 KB Output is correct
27 Correct 396 ms 9784 KB Output is correct
28 Correct 413 ms 12900 KB Output is correct
29 Correct 403 ms 11996 KB Output is correct
30 Correct 277 ms 8876 KB Output is correct
31 Correct 440 ms 12148 KB Output is correct
32 Correct 324 ms 12920 KB Output is correct
33 Correct 422 ms 12708 KB Output is correct
34 Correct 312 ms 12636 KB Output is correct
35 Correct 370 ms 11336 KB Output is correct
36 Correct 216 ms 7672 KB Output is correct
37 Correct 325 ms 13756 KB Output is correct
38 Correct 418 ms 13064 KB Output is correct
39 Correct 359 ms 13228 KB Output is correct