oj.uz

Submission #46220

# Submission time Handle Problem Language Result Execution time Memory
46220 2018-04-18T05:19:12 Z RayaBurong25_1 Sorting (IOI15_sorting) C++17
20 / 100
 16 ms 10344 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() - 1;
        xp = WhereIs[x][xp].second;
        yp = std::lower_bound(WhereIs[y].begin(), WhereIs[y].end(), i, compare) - 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 < 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:102: 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() - 1;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
sorting.cpp:56:102: 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() - 1;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 12 ms 9752 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 12 ms 9728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 12 ms 9752 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 12 ms 9728 KB Output is correct
8 Correct 14 ms 9976 KB Output is correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 13 ms 9984 KB Output is correct
12 Correct 10 ms 9856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Incorrect 9 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 9 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 12 ms 9752 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 12 ms 9728 KB Output is correct
8 Correct 14 ms 9976 KB Output is correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 11 ms 9856 KB Output is correct
11 Correct 13 ms 9984 KB Output is correct
12 Correct 10 ms 9856 KB Output is correct
13 Correct 11 ms 9728 KB Output is correct
14 Incorrect 9 ms 9728 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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