oj.uz

Submission #64697

# Submission time Handle Problem Language Result Execution time Memory
64697 2018-08-05T12:19:43 Z FLDutchman Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 24620 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]);
	FOR(i, 0, M){
		if(solve(i)) break;
	}
	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:57:2: note: in expansion of macro 'FOR'
  FOR(i, 0, swaps.size()){
  ^~~
sorting.cpp:60: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:61: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:66: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 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 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 4 ms 384 KB Output is correct
12 Correct 2 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 384 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 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 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 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 4 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 384 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 256 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 6 ms 896 KB Output is correct
22 Correct 6 ms 896 KB Output is correct
23 Correct 6 ms 896 KB Output is correct
24 Correct 6 ms 896 KB Output is correct
25 Correct 4 ms 908 KB Output is correct
26 Correct 5 ms 896 KB Output is correct
27 Correct 6 ms 896 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 652 KB Output is correct
2 Correct 58 ms 640 KB Output is correct
3 Correct 47 ms 640 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 15 ms 640 KB Output is correct
8 Correct 48 ms 640 KB Output is correct
9 Correct 50 ms 640 KB Output is correct
10 Correct 50 ms 640 KB Output is correct
11 Correct 40 ms 640 KB Output is correct
12 Correct 16 ms 640 KB Output is correct
13 Correct 36 ms 632 KB Output is correct
14 Correct 3 ms 640 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 652 KB Output is correct
2 Correct 58 ms 640 KB Output is correct
3 Correct 47 ms 640 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 15 ms 640 KB Output is correct
8 Correct 48 ms 640 KB Output is correct
9 Correct 50 ms 640 KB Output is correct
10 Correct 50 ms 640 KB Output is correct
11 Correct 40 ms 640 KB Output is correct
12 Correct 16 ms 640 KB Output is correct
13 Correct 36 ms 632 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Execution timed out 1067 ms 24620 KB Time limit exceeded
16 Halted 0 ms 0 KB -