oj.uz

Submission #64695

# Submission time Handle Problem Language Result Execution time Memory
64695 2018-08-05T12:18:54 Z FLDutchman Sorting (IOI15_sorting) C++14
0 / 100
 1000 ms 8424 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Expected EOLN
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Expected EOLN
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Expected EOLN
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Expected EOLN
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 8424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 8424 KB Time limit exceeded
2 Halted 0 ms 0 KB -