제출 #46223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46223		RayaBurong25_1	정렬하기 (IOI15_sorting)	C++17	74 / 100	1065 ms	39896 KiB

sorting

#include "sorting.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
int n;
// std::vector<std::pair<int, int> > XY;
std::vector<std::pair<int, int> > Seq[200005];
std::vector<std::pair<int, int> > WhereIs[200005];
std::pair<int, int> Swap[200005];
int K;
int NeedsToBe[200005];
int Cur[200005], CurInv[200005];
// int Sc[200005];
// int Scratch[200005];
// int WhereIs[200005];
int compare(std::pair<int, int> e, int v)
{
    return e.first < v;
}
int compare2(int v, std::pair<int, int> e)
{
    return v < e.first;
}
int can(int M)
{
    // printf("can %d\n", M);
    K = 0;
    int i, j;
    for (i = 0; i < n; i++)
    {
        j = std::lower_bound(Seq[i].begin(), Seq[i].end(), M, compare) - Seq[i].begin() - 1;
        // printf("NeedsToBe[%d] = %d\n", Seq[i][j].second, i);
        NeedsToBe[Seq[i][j].second] = i;
        Cur[i] = i;
        CurInv[i] = i;
        // Scratch[i] = Sc[i];
        // WhereIs[Sc[i]] = i;
    }
    int x, y, xp, yp;
    j = 0;
    for (i = 0; i < M; i++)
    {
        // xp = XY[i].first;
        // yp = XY[i].second;
        // x = Scratch[xp];
        // y = Scratch[yp];
        // Scratch[xp] = y;
        // Scratch[yp] = x;
        // WhereIs[x] = yp;
        // WhereIs[y] = xp;
        while (j < n && Cur[j] == NeedsToBe[j]) j++;
        if (j == n)
            break;

        // printf("j %d\n", j);
        x = j;
        y = CurInv[NeedsToBe[j]];
        xp = std::upper_bound(WhereIs[x].begin(), WhereIs[x].end(), i, compare2) - WhereIs[x].begin() - 1;
        xp = WhereIs[x][xp].second;
        yp = std::upper_bound(WhereIs[y].begin(), WhereIs[y].end(), i, compare2) - WhereIs[y].begin() - 1;
        yp = WhereIs[y][yp].second;
        // printf("x %d xp %d y %d yp %d\n", x, xp, y, yp);
        Swap[K] = {xp, yp};
        K++;
        xp = Cur[x];
        yp = Cur[y];
        // printf("xp %d yp %d\n", xp, yp);
        Cur[x] = yp;
        Cur[y] = xp;
        CurInv[xp] = y;
        CurInv[yp] = x;
    }
    while (j < n && Cur[j] == NeedsToBe[j]) j++;
    // printf("finally j %d\n", j);
    if (j == n)
        return 1;
    else
        return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    int i, j;
    for (i = 0; i < N; i++)
    {
        // Sc[i] = S[i];
        Seq[i].push_back({-1, S[i]});
        WhereIs[S[i]].push_back({-1, i});
    }
    int x, y;
    for (i = 0; i < N; i++)
    {
        // XY.push_back({X[i], Y[i]});
        if (X[i] == Y[i]) continue;
        x = Seq[X[i]].back().second;
        y = Seq[Y[i]].back().second;
        Seq[X[i]].push_back({i, y});
        Seq[Y[i]].push_back({i, x});
        WhereIs[y].push_back({i, X[i]});
        WhereIs[x].push_back({i, Y[i]});
    }
    // for (i = 0; i < N; i++)
    // {
    //     // printf("i%d : ", i);
    //     for (j = 0; j < Seq[i].size(); j++)
    //         // printf("(%d %d) ", Seq[i][j].first, Seq[i][j].second);
    //     // printf("\n");
    // }
    // for (i = 0; i < N; i++)
    // {
    //     // printf("i%d : ", i);
    //     for (j = 0; j < WhereIs[i].size(); j++)
    //         // printf("(%d %d) ", WhereIs[i][j].first, WhereIs[i][j].second);
    //     // printf("\n");
    // }
    int mn = -1, mx = N;
    int md;
    while (mn != mx)
    {
        if (mx - mn == 1)
        {
            can(mx);
            md = mx;
            break;
        }
        md = (mn + mx)/2;
        if (can(md))
            mx = md;
        else
            mn = md;
    }
    for (i = 0; i < K; i++)
    {
        P[i] = Swap[i].first;
        Q[i] = Swap[i].second;
    }
    for (; i < md; i++)
    {
        P[i] = 0;
    	Q[i] = 0;
    }
	return md;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int can(int)':
sorting.cpp:31:89: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
         j = std::lower_bound(Seq[i].begin(), Seq[i].end(), M, compare) - Seq[i].begin() - 1;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
sorting.cpp:58:103: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
         xp = std::upper_bound(WhereIs[x].begin(), WhereIs[x].end(), i, compare2) - WhereIs[x].begin() - 1;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
sorting.cpp:60:103: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
         yp = std::upper_bound(WhereIs[y].begin(), WhereIs[y].end(), i, compare2) - WhereIs[y].begin() - 1;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:82:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sorting.cpp:80:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^
sorting.cpp:116:9: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int md;
         ^~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 0 / 26