Submission #46225

#	Time	Username	Problem	Language	Result	Execution time	Memory
46225		RayaBurong25_1	Sorting (IOI15_sorting)	C++14	74 / 100	1043 ms	31672 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;
        if (XY[i].first != XY[i].second)
        {
            x = Scratch[XY[i].first];
            y = Scratch[XY[i].second];
            Scratch[XY[i].first] = y;
            Scratch[XY[i].second] = x;
            WhereIs[x] = XY[i].second;
            WhereIs[y] = XY[i].first;
        }
        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;
        // xp = WhereIs[x];
        // yp = WhereIs[y];
        // printf("x %d xp %d y %d yp %d\n", x, xp, y, yp);
        // Swap[K] = {xp, yp};
        Swap[K] = {WhereIs[x], WhereIs[y]};
        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;
    }
    // printf("K %d\n", K);
    for (i = 0; i < K; i++)
    {
        // printf("%d %d\n", Swap[i].first, Swap[i].second);
        P[i] = Swap[i].first;
        Q[i] = Swap[i].second;
    }
    for (; i < md; i++)
    {
        P[i] = 0;
    	Q[i] = 0;
    }
	return md;
}

Compilation message (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: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:88:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sorting.cpp:86: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:122: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