Submission #46217

#	Time	Username	Problem	Language	Result	Execution time	Memory
46217		RayaBurong25_1	Sorting (IOI15_sorting)	C++17	0 / 100	9 ms	5504 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> > Swap;
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 can(int M)
{
    // printf("can %d\n", M);
    Swap.resize(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++)
    {
        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 = WhereIs[j];
        yp = WhereIs[CurInv[NeedsToBe[j]]];
        // printf("x %d xp %d y %d yp %d\n", x, xp, y, yp);
        Swap.push_back({xp, yp});
        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]});
    }
    int x, y;
    for (i = 0; i < M; 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});
    }
    // 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");
    // }
    int mn = 0, mx = M;
    int md;
    while (mn != mx)
    {
        if (mx - mn == 1)
        {
            if (can(mn))
                md = mn;
            else if (can(mx))
                md = mx;
            break;
        }
        md = (mn + mx)/2;
        if (can(md))
            mx = Swap.size();
        else
            mn = md;
    }
    for (i = 0; i < Swap.size(); i++)
    {
        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:25: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:108:27: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             mx = Swap.size();
                  ~~~~~~~~~^~
sorting.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Swap.size(); i++)
                 ~~^~~~~~~~~~~~~
sorting.cpp:71:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sorting.cpp:95:9: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int md;
         ^~

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