oj.uz

Submission #46216

# Submission time Handle Problem Language Result Execution time Memory
46216 2018-04-18T04:52:55 Z RayaBurong25_1 Sorting (IOI15_sorting) C++17
0 / 100
 14 ms 9984 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> > 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++;

        // 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]});
        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 = 1, 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 = md;
        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

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:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Swap.size(); i++)
                 ~~^~~~~~~~~~~~~
sorting.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sorting.cpp:92: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 Runtime error 14 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5376 KB Output is correct
2 Correct 7 ms 5428 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct
4 Incorrect 9 ms 5504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5376 KB Output is correct
2 Correct 7 ms 5428 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct
4 Incorrect 9 ms 5504 KB Output isn't correct
5 Halted 0 ms 0 KB -