oj.uz

Submission #48224

# Submission time Handle Problem Language Result Execution time Memory
48224 2018-05-10T16:07:26 Z cheater2k Sorting (IOI15_sorting) C++17
36 / 100
 15 ms 996 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

int n, m;
int s[MAXN], pos[MAXN];
int cnt[MAXN];

void do_swap(int x, int y) {
	int p = s[x], q = s[y];
	swap(pos[p], pos[q]);
	swap(s[x], s[y]);
	//for (int i = 0; i < n; ++i) cerr << s[i] << ' '; cerr << endl;
}

bool is_sorted() {
	for (int i = 0; i < n; ++i) if (s[i] != i) return false;
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
  for (int i = 0; i < n; ++i) {
  	s[i] = S[i];
  	pos[s[i]] = i;
  }
  if (is_sorted()) return 0;

  for (int i = 0; i < m; ++i) {
  	++cnt[X[i]];
  	++cnt[Y[i]];
  }

  for (int i = 0; i < m; ++i) {
  	if (is_sorted()) return i;

  	do_swap(X[i], Y[i]);
  	--cnt[X[i]];
  	--cnt[Y[i]];

  	bool found = false;
  	for (int j = 0; j < n; ++j) {
  		if (pos[j] != j && cnt[j] == 0) {
  			found = true;
  			P[i] = j; Q[i] = pos[j];
  			do_swap(j, pos[j]);
  			break;
  		}
  	}

  	if (!found) P[i] = Q[i] = 0, do_swap(0, 0);
  }

  for (int i = 0; i < n; ++i) assert(s[i] == i);
  return m;
}

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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 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 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 428 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 428 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 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 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 128 KB Output is correct
21 Runtime error 13 ms 996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -