oj.uz

답안 #795330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
795330 2023-07-27T08:24:49 Z jasmin 정렬하기 (IOI15_sorting) C++17
74 / 100
 1000 ms 13476 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;

int cnt_cycle(vector<int>& s, int n){

    vector<bool> vis(n, false);
    int cnt=0;
    for(int v=0; v<n; v++){
        if(vis[v]) continue;
        
        cnt++;

        int mom=s[v];
        while(!vis[mom]){

            vis[mom]=true;
            mom=s[mom];
        }
    }

    return cnt;
}

int findSwapPairs(int n, int S[], int m, int x[], int y[], int p[], int q[]) {
    
    //initialize
    vector<int> s(n);
    for(int i=0; i<n; i++){
        s[i] = S[i];
    }

    //cnt minimal rounds
    int rounds=-1;
    int cnt = n-cnt_cycle(s, n);
    for(int i=0; i<m; i++){

        if(cnt<=i){
            rounds = i;
            break;
        }

        swap(s[x[i]], s[y[i]]);
        cnt = n-cnt_cycle(s, n);
    }

    if(rounds==-1 && cnt<=m){
        rounds=m;
    }
    assert(rounds!=-1);


    //find swaps
    deque<int> missing;
    vector<int> next(n);

    vector<bool> vis(n, false);
    for(int v=0; v<n; v++){
        if(vis[v]) continue;

        int mom = v;
        while(!vis[mom]){
            vis[mom]=true;

            missing.push_back(s[mom]);
            next[s[mom]] = s[s[mom]];

            mom=s[mom];
        }
        missing.pop_back(); //last in cycle doesn't need to be swapped anymore
    }

    vector<int> pos(n);
    for(int i=0; i<n; i++){
        pos[s[i]]=i;
    }

    for(int i=rounds-1; i>=0; i--){

        if(missing.empty()){

            p[i]=q[i]=0;
            continue;
        }

        int a=missing.front(); missing.pop_front();
        int b=next[a];

        //cout << a << " " << b << ": " << pos[a] << " " << pos[b] << "\n";

        p[i] = pos[a];
        q[i] = pos[b];

        swap(pos[s[x[i]]], pos[s[y[i]]]);
        swap(s[x[i]], s[y[i]]);
    }

    return rounds;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 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 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 440 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 3 ms 468 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 420 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 10 ms 416 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 8 ms 432 KB Output is correct
8 Correct 11 ms 420 KB Output is correct
9 Correct 10 ms 436 KB Output is correct
10 Correct 11 ms 468 KB Output is correct
11 Correct 11 ms 432 KB Output is correct
12 Correct 8 ms 436 KB Output is correct
13 Correct 15 ms 456 KB Output is correct
14 Correct 1 ms 444 KB Output is correct

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 420 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 10 ms 416 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 8 ms 432 KB Output is correct
8 Correct 11 ms 420 KB Output is correct
9 Correct 10 ms 436 KB Output is correct
10 Correct 11 ms 468 KB Output is correct
11 Correct 11 ms 432 KB Output is correct
12 Correct 8 ms 436 KB Output is correct
13 Correct 15 ms 456 KB Output is correct
14 Correct 1 ms 444 KB Output is correct
15 Execution timed out 1037 ms 13476 KB Time limit exceeded
16 Halted 0 ms 0 KB -