oj.uz

Submission #60187

# Submission time Handle Problem Language Result Execution time Memory
60187 2018-07-23T20:26:02 Z Flugan42 Sorting (IOI15_sorting) C++14
100 / 100
 425 ms 15876 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9223372036854775807
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  ll lo = -1, hi = N, mid;
  while (lo+1 < hi){
    mid = (lo+hi)/2;
    vi last; last.assign(N,0);
    rep(i,0,N) last[i] = S[i];
    rep(i,0,mid){
      ll t1 = last[X[i]];
      ll t2 = last[Y[i]];
      last[Y[i]] = t1;
      last[X[i]] = t2;
    }
    vi inv; inv.assign(N,0);
    rep(i,0,N) inv[last[i]] = i;
    ll cur = 0;
    rep(i,0,mid){
      while (cur < N && inv[cur] == cur) cur++;
      if (cur == N) break;
      ll s = last[cur],ls = inv[cur];
      last[ls] = s;
      last[cur] = cur;
      inv[cur] = cur;
      inv[s] = ls;
    }
    bool check = true;
    rep(i,0,N) if (inv[i] != i) check = false;
    if (check) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  if (hi == 0){
    bool check = true;
    rep(i,0,N) if (S[i] != i) check = false;
    if (check) return 0;
    else hi = 1;
  }
  vi last; last.assign(N,0);
  rep(i,0,N) last[i] = S[i];
  rep(i,0,hi){
    ll t1 = last[X[i]];
    ll t2 = last[Y[i]];
    last[Y[i]] = t1;
    last[X[i]] = t2;
  }
  vi inv; inv.assign(N,0);
  rep(i,0,N) inv[last[i]] = i;
  ll cur = 0;
  vii swap;
  rep(i,0,hi){
    while (cur < N && inv[cur] == cur) cur++;
    if (cur == N) break;
    ll s = last[cur],ls = inv[cur];
    swap.push_back(make_pair(s,cur));
    last[ls] = s;
    last[cur] = cur;
    inv[cur] = cur;
    inv[s] = ls;
  }
  while (sz(swap) < hi) swap.push_back(make_pair(0,0));
  last.assign(N,0);
  inv.assign(N,0);
  rep(i,0,N) last[i] = S[i];
  rep(i,0,N) inv[last[i]] = i;
  rep(i,0,hi){
    ll t1 = last[X[i]];
    ll t2 = last[Y[i]];
    last[Y[i]] = t1;
    last[X[i]] = t2;
    inv[t1] = Y[i];
    inv[t2] = X[i];
    //
    P[i] = inv[swap[i].first];
    Q[i] = inv[swap[i].second];
    last[P[i]] = swap[i].second;
    last[Q[i]] = swap[i].first;
    inv[swap[i].first] = Q[i];
    inv[swap[i].second] = P[i];
  }
	return hi;
}

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:92:29: warning: conversion to 'int' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
     P[i] = inv[swap[i].first];
                             ^
sorting.cpp:93:30: warning: conversion to 'int' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
     Q[i] = inv[swap[i].second];
                              ^
sorting.cpp:99:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return hi;
         ^~
sorting.cpp:19:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^
sorting.cpp: At global scope:
sorting.cpp:105:27: warning: '_outputFile' defined but not used [-Wunused-variable]
 static FILE *_inputFile, *_outputFile;
                           ^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 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 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 256 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 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 4 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 432 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 2 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 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 432 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 297 ms 14176 KB Output is correct
16 Correct 230 ms 14460 KB Output is correct
17 Correct 339 ms 15116 KB Output is correct
18 Correct 86 ms 8284 KB Output is correct
19 Correct 228 ms 12856 KB Output is correct
20 Correct 197 ms 13376 KB Output is correct
21 Correct 314 ms 13628 KB Output is correct
22 Correct 310 ms 15292 KB Output is correct
23 Correct 412 ms 15564 KB Output is correct
24 Correct 296 ms 15448 KB Output is correct
25 Correct 353 ms 15344 KB Output is correct
26 Correct 207 ms 13408 KB Output is correct
27 Correct 208 ms 12800 KB Output is correct
28 Correct 422 ms 15268 KB Output is correct
29 Correct 250 ms 14900 KB Output is correct
30 Correct 140 ms 11056 KB Output is correct
31 Correct 371 ms 15004 KB Output is correct
32 Correct 353 ms 15252 KB Output is correct
33 Correct 337 ms 15424 KB Output is correct
34 Correct 337 ms 15488 KB Output is correct
35 Correct 289 ms 13040 KB Output is correct
36 Correct 90 ms 8956 KB Output is correct
37 Correct 425 ms 15876 KB Output is correct
38 Correct 344 ms 15260 KB Output is correct
39 Correct 279 ms 15316 KB Output is correct