oj.uz

답안 #532818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532818 2022-03-04T02:42:18 Z ivan24 정렬하기 (IOI15_sorting) C++14
8 / 100
 3 ms 844 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

const ll INF = 1e18;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    p[0] = 0; q[0] = 1;
    bool perfect = true;
    for (ll i = 0; n > i; i++){
        if (s[i] != i) perfect = false;
    }
    if (perfect) return 0;

    ll lo = 1,hi = m,md;
    md = (lo+hi/2);
    while (hi >= lo){
        md = (lo+hi)/2;
        //cout << "md: " << md << endl;
        vi v,v_idx;
        v.resize(n);
        v_idx.resize(n);
        for (ll i = 0; n > i; i++){
            v[i] = s[i]; v_idx[v[i]] = i;
        }
        for (ll i = 0; md > i; i++){
            swap(v[x[i]],v[y[i]]);
            swap(v_idx[v[x[i]]],v_idx[v[y[i]]]);
        }
        vi cur,cur_idx;
        cur.resize(n);
        cur_idx.resize(n);
        vii swaps;
        swaps.assign(md,ii(0,0));
        for (ll i = 0; n > i; i++){
            cur[i] = i; cur_idx[i] = i;
        }
        /*
        cout << "v: ";
        for (auto i: v) cout << i << " ";
        cout << endl;
        cout << "v_idx: ";
        for (auto i: v_idx) cout << i << " ";
        cout << endl;
        cout << "cur: ";
        for (auto i: cur) cout << i << " ";
        cout << endl;
        cout << "cur_idx: ";
        for (auto i: cur_idx) cout << i << " ";
        cout << endl;
        */
        ll ptr = 0;
        for (ll i = md-1; i >= 0; i--){
            if (ptr >= n) continue;
            while (n > ptr && cur_idx[ptr] == v_idx[ptr]) ptr++;
            swaps.emplace_back(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
            swap(cur[cur_idx[ptr]],cur[cur_idx[v[cur_idx[ptr]]]]);
            swap(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
            /*
            cout << "swapped: " << cur_idx[ptr] << " and " << cur_idx[v[cur_idx[ptr]]] << " ptr: " << ptr << endl;
            cout << "cur: ";
            for (auto i: cur) cout << i << " ";
            cout << endl;
            cout << "cur_idx: ";
            for (auto i: cur_idx) cout << i << " ";
            cout << endl;
            */

            swap(v_idx[v[x[i]]], v_idx[v[y[i]]]);
            swap(v[x[i]],v[y[i]]);
            swap(cur_idx[cur[x[i]]],cur_idx[cur[y[i]]]);
            swap(cur[x[i]],cur[y[i]]);
        }
        bool works = true;
        for (ll i = 0; n > i; i++) works = works && (cur[i] == v[i]);
        /*
        cout << "after: \n";
        cout << "v: ";
        for (auto i: v) cout << i << " ";
        cout << endl;
        cout << "v_idx: ";
        for (auto i: v_idx) cout << i << " ";
        cout << endl;
        cout << "cur: ";
        for (auto i: cur) cout << i << " ";
        cout << endl;
        cout << "cur_idx: ";
        for (auto i: cur_idx) cout << i << " ";
        cout << endl;
        */
        if (works){
            hi = md;
            reverse(swaps.begin(),swaps.end());
            for (ll i = 0; md > i; i++){
                p[i] = swaps[i].F;
                q[i] = swaps[i].S;
            }
        }else
            lo = md+1;
        if (hi == lo && hi == md) return md;
    }
	return md;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 | #define F first
sorting.cpp:112:33: note: in expansion of macro 'F'
  112 |                 p[i] = swaps[i].F;
      |                                 ^
sorting.cpp:12:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 | #define S second
sorting.cpp:113:33: note: in expansion of macro 'S'
  113 |                 q[i] = swaps[i].S;
      |                                 ^
sorting.cpp:117:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |         if (hi == lo && hi == md) return md;
      |                                          ^~
sorting.cpp:119:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return md;
      |         ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 248 KB Output is correct
4 Correct 0 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 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Runtime error 1 ms 460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 248 KB Output is correct
4 Correct 0 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 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Runtime error 1 ms 460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 496 KB Output is correct
2 Correct 3 ms 532 KB Output is correct
3 Runtime error 1 ms 844 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 496 KB Output is correct
2 Correct 3 ms 532 KB Output is correct
3 Runtime error 1 ms 844 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -