oj.uz

Submission #432976

# Submission time Handle Problem Language Result Execution time Memory
432976 2021-06-18T16:36:32 Z wiwiho Sorting (IOI15_sorting) C++14
56 / 100
 1000 ms 8616 KB 
#include "sorting.h"
 
#include <bits/stdc++.h>
 
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define Sc second
#define eb emplace_back
 
using namespace std;
 
typedef long long ll;
 
using pii = pair<int, int>;
 
const ll MOD = 1000000007;

vector<pii> ans;
bool calc(int n, int S[], int m, int X[], int Y[]){
    ans.clear();

    vector<int> s(n);
    for(int i = 0; i < n; i++) s[i] = S[i];
 
    vector<int> num(n);
    vector<int> pos(n);
    for(int i = 0; i < n; i++) num[i] = pos[i] = i;
    for(int i = 0; i < m; i++){
        swap(num[pos[X[i]]], num[pos[Y[i]]]);
        swap(pos[X[i]], pos[Y[i]]);
    }
 
    int cnt = 0;
    vector<int> now(n), np(n);
    for(int i = 0; i < n; i++) now[i] = i, np[i] = i;
    for(int i = 0; i < n; i++){
        while(s[i] != num[i]){
            if(cnt >= m) return false;
            swap(now[np[X[cnt]]], now[np[Y[cnt]]]);
            swap(np[X[cnt]], np[Y[cnt]]);
            cnt++;
            ans.eb(mp(now[i], now[pos[s[i]]]));
            swap(s[i], s[pos[s[i]]]);
        }
    }
    while(ans.size() < m) ans.eb(mp(0, 0));
    //cerr << "test " << m << "\n";
    //printv(num, cerr);
    //printv(s, cerr);
    return true;
}
 
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {

    int mn = m + 1, mnp = -1;
    for(int i = 0; i <= m; i++){
        if(calc(n, S, i, X, Y)){
            if(ans.size() < mn){
                mn = ans.size();
                mnp = i;
            }
        }
    }
    calc(n, S, mnp, X, Y);
 
    for(int i = 0; i < ans.size(); i++){
        P[i] = ans[i].F;
        Q[i] = ans[i].Sc;
    }
    
	return ans.size();
}

Compilation message

sorting.cpp: In function 'bool calc(int, int*, int, int*, int*)':
sorting.cpp:50: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]
   50 |     while(ans.size() < m) ans.eb(mp(0, 0));
      |           ~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:62:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |             if(ans.size() < mn){
      |                ~~~~~~~~~~~^~~~
sorting.cpp:63:30: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |                 mn = ans.size();
      |                      ~~~~~~~~^~
sorting.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
sorting.cpp:75:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  return ans.size();
      |         ~~~~~~~~^~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 62 ms 332 KB Output is correct
11 Correct 59 ms 344 KB Output is correct
12 Correct 56 ms 356 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 56 ms 476 KB Output is correct
4 Correct 60 ms 352 KB Output is correct
5 Correct 60 ms 348 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 62 ms 332 KB Output is correct
11 Correct 59 ms 344 KB Output is correct
12 Correct 56 ms 356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 56 ms 476 KB Output is correct
16 Correct 60 ms 352 KB Output is correct
17 Correct 60 ms 348 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Execution timed out 1089 ms 640 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 464 KB Output is correct
2 Correct 439 ms 424 KB Output is correct
3 Correct 431 ms 572 KB Output is correct
4 Correct 480 ms 480 KB Output is correct
5 Correct 516 ms 576 KB Output is correct
6 Correct 479 ms 708 KB Output is correct
7 Correct 511 ms 484 KB Output is correct
8 Correct 453 ms 452 KB Output is correct
9 Correct 469 ms 472 KB Output is correct
10 Correct 460 ms 532 KB Output is correct
11 Correct 485 ms 588 KB Output is correct
12 Correct 493 ms 400 KB Output is correct
13 Correct 474 ms 588 KB Output is correct
14 Correct 236 ms 452 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 464 KB Output is correct
2 Correct 439 ms 424 KB Output is correct
3 Correct 431 ms 572 KB Output is correct
4 Correct 480 ms 480 KB Output is correct
5 Correct 516 ms 576 KB Output is correct
6 Correct 479 ms 708 KB Output is correct
7 Correct 511 ms 484 KB Output is correct
8 Correct 453 ms 452 KB Output is correct
9 Correct 469 ms 472 KB Output is correct
10 Correct 460 ms 532 KB Output is correct
11 Correct 485 ms 588 KB Output is correct
12 Correct 493 ms 400 KB Output is correct
13 Correct 474 ms 588 KB Output is correct
14 Correct 236 ms 452 KB Output is correct
15 Execution timed out 1084 ms 8616 KB Time limit exceeded
16 Halted 0 ms 0 KB -