oj.uz

Submission #64700

# Submission time Handle Problem Language Result Execution time Memory
64700 2018-08-05T12:21:48 Z FLDutchman Sorting (IOI15_sorting) C++14
100 / 100
 434 ms 32368 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mod = 1e9+7;

int N, M;
vi S, X, Y, P, Q;
vii swaps;

bool solve(int R){
	swaps.clear();
	vi perm = S;
	FOR(i, 0, R) swap(perm[X[i]], perm[Y[i]]);
	// VALUES that should be swapped
	vi idx(N);
	FOR(i, 0, N) idx[perm[i]] = i;
	int cnt = 0;
	FOR(i, 0, N){
		if(i != perm[i]) {
			cnt++;
			swaps.pb({perm[i], i});
			//cout << perm[i] << " " << i << endl;
			int pi = perm[i]; 
			swap(perm[i], perm[idx[i]]);
			swap(idx[i], idx[pi]);
		}
	}
	FOR(i, swaps.size(), R) swaps.pb({0, 0});
	//for(int i : perm) cout << i << " ";
	//cout << endl;
	return cnt <= R;
}

INT findSwapPairs(INT n, INT s[], INT m, INT x[], INT y[], INT p[], INT q[]) {
	N = n; M = m;
    FOR(i, 0, N) S.pb(s[i]);
	FOR(i, 0, M) X.pb(x[i]), Y.pb(y[i]);

	int lb = -1, rb = M;
	while(lb + 1 != rb){
		int mb = (lb+rb)/2;
		if(solve(mb)) rb = mb;
		else lb = mb;
	}
	solve(rb);

	vi idx(N);
	FOR(i, 0, N) idx[S[i]] = i;
	FOR(i, 0, swaps.size()){
		swap(idx[S[X[i]]], idx[S[Y[i]]]);
		swap(S[X[i]], S[Y[i]]);
		p[i] = idx[swaps[i].fst];
		q[i] = idx[swaps[i].snd];
		swap(S[idx[swaps[i].fst]], S[idx[swaps[i].snd]]);
		swap(idx[swaps[i].fst], idx[swaps[i].snd]);
	}

	return swaps.size();
}

Compilation message

sorting.cpp: In function 'INT findSwapPairs(INT, INT*, INT, INT*, INT*, INT*, INT*)':
sorting.cpp:8:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
sorting.cpp:63:2: note: in expansion of macro 'FOR'
  FOR(i, 0, swaps.size()){
  ^~~
sorting.cpp:66:26: warning: conversion to 'INT {aka int}' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
   p[i] = idx[swaps[i].fst];
                          ^
sorting.cpp:67:26: warning: conversion to 'INT {aka int}' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
   q[i] = idx[swaps[i].snd];
                          ^
sorting.cpp:72:19: warning: conversion to 'INT {aka int}' from 'std::vector<std::pair<long long int, long long int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return swaps.size();
         ~~~~~~~~~~^~

Subtask #1
8.0 / 8.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 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 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 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 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 512 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 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 256 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 3 ms 256 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 3 ms 1024 KB Output is correct
22 Correct 5 ms 1024 KB Output is correct
23 Correct 4 ms 1024 KB Output is correct
24 Correct 4 ms 1024 KB Output is correct
25 Correct 4 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 3 ms 1024 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 297 ms 30164 KB Output is correct
16 Correct 302 ms 30420 KB Output is correct
17 Correct 434 ms 31388 KB Output is correct
18 Correct 105 ms 30924 KB Output is correct
19 Correct 255 ms 31904 KB Output is correct
20 Correct 294 ms 32332 KB Output is correct
21 Correct 229 ms 32348 KB Output is correct
22 Correct 376 ms 31572 KB Output is correct
23 Correct 307 ms 31956 KB Output is correct
24 Correct 360 ms 31700 KB Output is correct
25 Correct 395 ms 31572 KB Output is correct
26 Correct 300 ms 32212 KB Output is correct
27 Correct 261 ms 31828 KB Output is correct
28 Correct 426 ms 32004 KB Output is correct
29 Correct 390 ms 31656 KB Output is correct
30 Correct 198 ms 31964 KB Output is correct
31 Correct 389 ms 31948 KB Output is correct
32 Correct 343 ms 31316 KB Output is correct
33 Correct 391 ms 31700 KB Output is correct
34 Correct 293 ms 31688 KB Output is correct
35 Correct 221 ms 31564 KB Output is correct
36 Correct 93 ms 32368 KB Output is correct
37 Correct 359 ms 32212 KB Output is correct
38 Correct 385 ms 31444 KB Output is correct
39 Correct 392 ms 31656 KB Output is correct