oj.uz

Submission #46221

# Submission time Handle Problem Language Result Execution time Memory
46221 2018-04-18T05:22:06 Z RayaBurong25_1 Sorting (IOI15_sorting) C++17
0 / 100
 15 ms 10240 KB 
#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 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::lower_bound(WhereIs[x].begin(), WhereIs[x].end(), i, compare) - WhereIs[x].begin();
        xp = WhereIs[x][xp].second;
        yp = std::lower_bound(WhereIs[y].begin(), WhereIs[y].end(), i, compare) - WhereIs[y].begin();
        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 < 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});
        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");
    // }
    int mn = -1, mx = M;
    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;
}

Compilation message

sorting.cpp: In function 'int can(int)':
sorting.cpp:27: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:54:81: 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::lower_bound(WhereIs[x].begin(), WhereIs[x].end(), i, compare) - WhereIs[x].begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
sorting.cpp:56:81: 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::lower_bound(WhereIs[y].begin(), WhereIs[y].end(), i, compare) - WhereIs[y].begin();
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:78:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sorting.cpp:105:9: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int md;
         ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Incorrect 11 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Incorrect 11 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Incorrect 12 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Incorrect 11 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 10240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 10240 KB Output isn't correct
2 Halted 0 ms 0 KB -