oj.uz

Submission #67942

# Submission time Handle Problem Language Result Execution time Memory
67942 2018-08-15T14:57:06 Z funcsr Sorting (IOI15_sorting) C++17
74 / 100
 39 ms 11000 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[100000];
bool used[100000];
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 {};
  return ret;
}

int rev[100000];
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);
  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:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(swaps.size() <= R);
          ~~~~~~~~~~~~~^~~~
sorting.cpp:57: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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 3 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 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 3 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 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 4 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 512 KB Output is correct
27 Correct 3 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 3 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 484 KB Output is correct
14 Correct 4 ms 384 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 484 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Runtime error 39 ms 11000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -