oj.uz

Submission #257860

# Submission time Handle Problem Language Result Execution time Memory
257860 2020-08-04T22:48:26 Z shrek12357 Sorting (IOI15_sorting) C++14
100 / 100
 378 ms 22740 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "sorting.h"
 
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
 
const ll H = 1e6 + 11;
 
//ifstream in(".in");
//ofstream out(".out");
 
int pos[H], n, m;
pi query[H], ans[H], a[H];
 
bool check(int t, int S[]){
 
    int in[n + 11], out[n + 11];
 
    for(int i = 0; i < n; i++){
        in[i] = out[i] = S[i];
    }
 	int adjList[n + 5]; // can optimize later
	for (int i = 0; i < n; i++) {
		adjList[i] = S[i];
	}
    for(int i = 0; i < t; i++){
        swap(out[query[i].ff], out[query[i].ss]);
    }
 
    bool viz[n + 11];
    memset(viz, 0, sizeof(viz));
 
    int k = 0;
    for(int i = 0; i < n; i++){
 
        if(viz[i])continue;
 
        vector<int>cur;
 
        int v = out[i];
        while(v != i){
            cur.push_back(v);
            v = out[v];
        }
        cur.push_back(v);
 
        for(int j = sz(cur) - 1; j > 0; j--){
            a[k++] = {cur[0], cur[j]};
        }
 
        for(auto it : cur)viz[it] = 1;
    }
 
    if(k > t)return 0;
 
    for (int i = 0; i < n; ++i){
        pos[in[i]] = i;
    }
 
    for(int i = 0; i < k; i++){
 
        //His move
        int x = query[i].ff, y = query[i].ss;
        swap(in[x], in[y]);
        pos[in[x]] = x;
        pos[in[y]] = y;
 
        //My move
        x = pos[a[i].ff], y = pos[a[i].ss];
        swap(in[x], in[y]);
        pos[in[x]] = x;
        pos[in[y]] = y;
 
        ans[i] = {x, y};
    }
 
    while(k < t)ans[k++] = {0, 0};
 
    return 1;
} 
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 < m; i++){
      query[i].first = X[i];
      query[i].second = Y[i];
    }
  	int lo = -1;
	int hi = M;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid, S)) {
			hi = mid;
		}
		else {
			lo = mid;
		}
		//toChange.clear();
	}
	check(hi, S);
	//getAns(hi, S, N, X, Y);
	for (int i = 0; i < hi; i++) {
		P[i] = ans[i].first;
		Q[i] = ans[i].second;
	}
	return hi;
}

Compilation message

sorting.cpp: In function 'bool check(int, int*)':
sorting.cpp:32:7: warning: variable 'adjList' set but not used [-Wunused-but-set-variable]
   int adjList[n + 5]; // can optimize later
       ^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 265 ms 20276 KB Output is correct
16 Correct 318 ms 19984 KB Output is correct
17 Correct 313 ms 21828 KB Output is correct
18 Correct 218 ms 17112 KB Output is correct
19 Correct 319 ms 20040 KB Output is correct
20 Correct 347 ms 20160 KB Output is correct
21 Correct 326 ms 20324 KB Output is correct
22 Correct 288 ms 21592 KB Output is correct
23 Correct 305 ms 22740 KB Output is correct
24 Correct 346 ms 22412 KB Output is correct
25 Correct 356 ms 22040 KB Output is correct
26 Correct 325 ms 19320 KB Output is correct
27 Correct 290 ms 18424 KB Output is correct
28 Correct 342 ms 21160 KB Output is correct
29 Correct 375 ms 20484 KB Output is correct
30 Correct 295 ms 17444 KB Output is correct
31 Correct 378 ms 20984 KB Output is correct
32 Correct 317 ms 21320 KB Output is correct
33 Correct 339 ms 22272 KB Output is correct
34 Correct 313 ms 21304 KB Output is correct
35 Correct 316 ms 19156 KB Output is correct
36 Correct 199 ms 16120 KB Output is correct
37 Correct 343 ms 22068 KB Output is correct
38 Correct 325 ms 21192 KB Output is correct
39 Correct 342 ms 21292 KB Output is correct