oj.uz

Submission #1088689

# Submission time Handle Problem Language Result Execution time Memory
1088689 2024-09-14T19:20:33 Z gustavo_d Sorting (IOI15_sorting) C++17
0 / 100
 1000 ms 348 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int findSwapPairs(
	int N, int S[], int M, int X[], int Y[], int P[], int Q[]
) {
	if (N == 1) return 0;

	vector<int> p_ans(M), q_ans(M);
	for (int ops=0; ops<=M; ops++) {
		vector<int> p, q;
		int m = ops;
		int pt = 0;
		int t=0;
	    for (; t<m and pt < N; t++, pt++) {
	    	bool sorted = true;
			for (int i=1; i<N; i++) {
				if (S[i] < S[i-1]) sorted = false;
			}
			if (sorted) break;

			swap(S[X[t]], S[Y[t]]);

	    	int permut[N];
	    	for (int i=0; i<N; i++) permut[i] = i;
	    	for (int i=t+1; i<m; i++) {
	    		swap(permut[X[i]], permut[Y[i]]);
	    	}
	    	int a=0, b=0;
	    	for (int i=0; i<N; i++) {
	    		if (S[i] == pt) a = i;
	    	}
	    	b = permut[pt];
	    	if (a == b) {
	    		t--;
	    		continue;
	    	}
	    	swap(S[a], S[b]);
	    	p.push_back(a);
	    	q.push_back(b);
	    }

    	bool sorted = true;
		for (int i=1; i<N; i++) {
			if (S[i] < S[i-1]) sorted = false;
		}
		if (!sorted) continue;
	    // cout << "ans = ";
	    // for (int i=0; i<N; i++) cout << S[i] << ' ';
	    // cout << endl;

	    for (; t<m; t++) {
	    	p.push_back(0);
	    	q.push_back(0);
	    }
	    if (p.size() <= p_ans.size()) {
	    	swap(p, p_ans);
	    	swap(q, q_ans);
	    }
	}
	for (int i=0; i<(int)p_ans.size(); i++) {
		P[i] = p_ans[i];
		Q[i] = q_ans[i];
	}
	return (int)p_ans.size();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 348 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 1060 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -