oj.uz

Submission #781540

# Submission time Handle Problem Language Result Execution time Memory
781540 2023-07-13T07:46:07 Z vjudge1 Sorting (IOI15_sorting) C++17
100 / 100
 153 ms 27396 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 600005
#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:39: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]
   39 |     if (swaps.size() <= k) return 1;
      |         ~~~~~~~~~~~~~^~~~
sorting.cpp:18:9: warning: unused variable 'todo' [-Wunused-variable]
   18 |     int todo = 0;
      |         ^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |     for (int i = 0; i < m; i++)
      |     ^~~
sorting.cpp:52:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |   int ans = 0;
      |   ^~~
sorting.cpp:59:7: warning: unused variable 'tmp' [-Wunused-variable]
   59 |   int tmp = check(ans);
      |       ^~~
sorting.cpp:61:9: warning: unused variable 'todo' [-Wunused-variable]
   61 |     int todo = 0;
      |         ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 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 0 ms 212 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 0 ms 340 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 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 260 KB Output is correct
15 Correct 0 ms 340 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 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Correct 1 ms 588 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 588 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 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 2 ms 492 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 464 KB Output is correct
12 Correct 1 ms 496 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 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 2 ms 492 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 464 KB Output is correct
12 Correct 1 ms 496 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 128 ms 16536 KB Output is correct
16 Correct 131 ms 24660 KB Output is correct
17 Correct 143 ms 25964 KB Output is correct
18 Correct 59 ms 22028 KB Output is correct
19 Correct 104 ms 24480 KB Output is correct
20 Correct 108 ms 25332 KB Output is correct
21 Correct 108 ms 25328 KB Output is correct
22 Correct 124 ms 21452 KB Output is correct
23 Correct 135 ms 27016 KB Output is correct
24 Correct 150 ms 26616 KB Output is correct
25 Correct 153 ms 26300 KB Output is correct
26 Correct 110 ms 24728 KB Output is correct
27 Correct 107 ms 22784 KB Output is correct
28 Correct 137 ms 26272 KB Output is correct
29 Correct 143 ms 25696 KB Output is correct
30 Correct 90 ms 22364 KB Output is correct
31 Correct 135 ms 26304 KB Output is correct
32 Correct 142 ms 26080 KB Output is correct
33 Correct 146 ms 26556 KB Output is correct
34 Correct 143 ms 26508 KB Output is correct
35 Correct 101 ms 24152 KB Output is correct
36 Correct 54 ms 21364 KB Output is correct
37 Correct 153 ms 27396 KB Output is correct
38 Correct 153 ms 26260 KB Output is correct
39 Correct 140 ms 26448 KB Output is correct