oj.uz

Submission #781538

# Submission time Handle Problem Language Result Execution time Memory
781538 2023-07-13T07:45:24 Z vjudge1 Sorting (IOI15_sorting) C++17
74 / 100
 40 ms 22588 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define K 200005
#define LOGN 20
int n, s[K], m, x[K], y[K], p[K], q[K];
vector<pii> swaps;

int check(int k){
	vector<int> res(n), ind(n);
    int todo = 0;
    for (int i = 0; i < n; i++)
    {
    	res[i] = s[i];
    	ind[s[i]] = i;
    }
   	swaps.clear();
    for (int i = 0; i < k; i++){
    	swap(res[x[i]], res[y[i]]);
    	ind[res[x[i]]] = x[i], ind[res[y[i]]] = y[i];
    }

    for (int i = 0; i < n; i++){
    	if (res[i] != i) {
    		int a = i, b = ind[i];
    		swaps.pb({res[i], i});
    		swap(res[a], res[b]);
    		ind[res[a]] = a, ind[res[b]] = b;
    	}
    }

    if (swaps.size() <= k) return 1;
    return 0;
}


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];
    }
    for (int i = 0; i < m; i++)
    	x[i] = X[i], y[i] = Y[i];

 	int ans = 0;
 	for (int i = LOGN; i >= 0; i--){
 		int tmp = ans + (1<<i);
 		if (tmp <= m && check(tmp) == 0) ans = tmp;
 	}   

 	if (check(ans) == 0) ans++;
 	int tmp = check(ans);
 	vector<int> res(N), ind(N);
    int todo = 0;
    for (int i = 0; i < n; i++)
    {
    	res[i] = s[i];
    	ind[s[i]] = i;
    }
/*
    for (auto i : swaps){
    	cout<<i.st<<sp<<i.nd<<endl;
    }*/
    reverse(swaps.begin(), swaps.end());
 	for (int i = 0; i < ans; i++){
 		/*
 		for (auto i : res) cout<<i<<sp;
 		cout<<endl;*/
 		swap(res[X[i]], res[Y[i]]);
    	ind[res[X[i]]] = X[i], ind[res[Y[i]]] = Y[i];
    	if (swaps.empty()){
    		P[i] = 0, Q[i] = 0;
    	}
    	else{
    		int a = swaps.back().st, b = swaps.back().nd;
    		swaps.pop_back();
    		P[i] = ind[a], Q[i] = ind[b];
    		swap(res[P[i]], res[Q[i]]);
    		ind[res[P[i]]] = P[i], ind[res[Q[i]]] = Q[i];
    	}
 	}
 	return ans;
 }

Compilation message

sorting.cpp: In function 'int check(int)':
sorting.cpp:38:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     if (swaps.size() <= k) return 1;
      |         ~~~~~~~~~~~~~^~~~
sorting.cpp:17:9: warning: unused variable 'todo' [-Wunused-variable]
   17 |     int todo = 0;
      |         ^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:48:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   48 |     for (int i = 0; i < m; i++)
      |     ^~~
sorting.cpp:51:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |   int ans = 0;
      |   ^~~
sorting.cpp:58:7: warning: unused variable 'tmp' [-Wunused-variable]
   58 |   int tmp = check(ans);
      |       ^~~
sorting.cpp:60:9: warning: unused variable 'todo' [-Wunused-variable]
   60 |     int todo = 0;
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 316 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 576 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 2 ms 580 KB Output is correct
14 Correct 1 ms 396 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 2 ms 580 KB Output is correct
14 Correct 1 ms 396 KB Output is correct
15 Runtime error 40 ms 22588 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -