oj.uz

Submission #314621

# Submission time Handle Problem Language Result Execution time Memory
314621 2020-10-20T13:16:24 Z talant117408 Sorting (IOI15_sorting) C++17
100 / 100
 386 ms 21068 KB 
#include "sorting.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
inline bool isvowel(char ch){
	ch = tolower(ch);
	return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
 
inline bool isprime(int n){
	if(n < 2 || (n%2 == 0 && n != 2)) return false;
	for(int i = 3; i*i <= n; i++)
		if(n%i == 0) return false;
	return true;
}

const int NN = 6e5+7;
int S[NN], X[NN], Y[NN], tmpS[NN], tmpos[NN];
int n;
vector <pii> res1;

bool check(int poss){
    int j;
    vector <pii> sws;
    
    for(j = 0; j < n; j++)
        tmpS[j] = S[j];
    for(j = 0; j < poss; j++)
        swap(tmpS[X[j]], tmpS[Y[j]]);
    for(j = 0; j < n; j++)
        tmpos[tmpS[j]] = j;
    
    for(j = 0; j < n; j++){
        if(tmpos[j] == j) continue;
        sws.pb(mp(tmpS[j], tmpS[tmpos[j]]));
        swap(tmpS[j], tmpS[tmpos[j]]);
        swap(tmpos[tmpS[j]], tmpos[tmpS[tmpos[j]]]);
    }
    if(sz(sws) <= poss){
        
        for(j = 0; j < n; j++){
            tmpS[j] = S[j];
            tmpos[S[j]] = j;
        }
        for(j = 0; j < sz(sws); j++){
            swap(tmpS[X[j]], tmpS[Y[j]]);
            swap(tmpos[tmpS[X[j]]], tmpos[tmpS[Y[j]]]);
            res1.pb(mp(tmpos[sws[j].first], tmpos[sws[j].second]));
            swap(tmpS[tmpos[sws[j].first]], tmpS[tmpos[sws[j].second]]);
            swap(tmpos[tmpS[tmpos[sws[j].first]]], tmpos[tmpS[tmpos[sws[j].second]]]);
        }
        
        while(sz(res1) < poss){
            res1.pb(mp(0, 0));
        }
        return 1;
    }
    return 0;
}
 
int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]) {
    
    int i;
    n = N;
    for(i = 0; i < N; i++){
        S[i] = s[i];
    }
    for(i = 0; i < M; i++){
        X[i] = x[i];
        Y[i] = y[i];
    }
    
    int l = 0, r = M;
    int mn = 2e9;
    while(l <= r){
        int mid = (l+r) >> 1;
        res1.clear();
        if(check(mid)){
            mn = min(mid, mn);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    
    for(i = 0; i < mn; i++){
        P[i] = res1[i].first;
        Q[i] = res1[i].second;
    }
    
    return mn;
}

Compilation message

sorting.cpp: In function 'bool isvowel(char)':
sorting.cpp:23:14: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   23 |  ch = tolower(ch);
      |       ~~~~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 384 KB Output is correct
5 Correct 1 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 1 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 0 ms 384 KB Output is correct
5 Correct 1 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 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 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 1 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 0 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 384 KB Output is correct
5 Correct 1 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 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 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 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 768 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 2 ms 768 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 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 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 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 283 ms 17448 KB Output is correct
16 Correct 333 ms 19252 KB Output is correct
17 Correct 342 ms 20096 KB Output is correct
18 Correct 124 ms 19184 KB Output is correct
19 Correct 228 ms 20196 KB Output is correct
20 Correct 244 ms 20784 KB Output is correct
21 Correct 221 ms 20776 KB Output is correct
22 Correct 287 ms 20824 KB Output is correct
23 Correct 317 ms 20868 KB Output is correct
24 Correct 362 ms 20528 KB Output is correct
25 Correct 381 ms 20268 KB Output is correct
26 Correct 228 ms 20840 KB Output is correct
27 Correct 210 ms 20044 KB Output is correct
28 Correct 319 ms 20348 KB Output is correct
29 Correct 334 ms 19892 KB Output is correct
30 Correct 156 ms 18920 KB Output is correct
31 Correct 353 ms 20208 KB Output is correct
32 Correct 307 ms 20296 KB Output is correct
33 Correct 386 ms 20476 KB Output is correct
34 Correct 331 ms 20428 KB Output is correct
35 Correct 228 ms 20040 KB Output is correct
36 Correct 81 ms 18536 KB Output is correct
37 Correct 363 ms 21068 KB Output is correct
38 Correct 353 ms 20264 KB Output is correct
39 Correct 350 ms 20580 KB Output is correct