Submission #937538

#	Time	Username	Problem	Language	Result	Execution time	Memory
937538		danikoynov	Scales (IOI15_scales)	C++14	55.56 / 100	1 ms	500 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>

using namespace std;

void init(int T)
{
    /* ... */
}

void sort_range(int l, int r, int w[])
{
    int a = w[l], b = w[l + 1], c = w[r];
    ///cout << "sort range " << a << " " << b << " " << c << endl;
    int mid = getMedian(a, b, c);
    int low = getLightest(a, b, c);
    int high = a;
    if (low == a || mid == a)
    {
        high = b;
        if (mid == b || low == b)
            high = c;
    }

    w[l] = low;
    w[l + 1] = mid;
    w[r] = high;
}

void merge_sort(int w[])
{
    vector < int > res;
    int lf = 0, rf = 3;

    int lightest = getLightest(w[0], w[1], w[3]);
    if (lightest == w[0])
        lf ++;
    else
        rf ++;
    res.push_back(lightest);
    while(lf <= 2 && rf <= 5 && (3 - lf + 6 - rf > 3))
    {
        if (getHeaviest(w[lf], w[rf], lightest) == w[lf])
            res.push_back(w[rf ++]);
        else
            res.push_back(w[lf ++]);
    }

    if (rf > 5)
    while(lf <= 2)
        res.push_back(w[lf ++]);
    if (lf > 5)
    while(rf <= 5)
        res.push_back(w[rf ++]);

    if (lf == 1)
    {
        int mid = getMedian(w[lf], w[lf + 1], w[rf]);
        if (mid == w[lf])
        {
            res.push_back(w[rf]);
            res.push_back(w[lf]);
            res.push_back(w[lf + 1]);
        }
        else
        if (mid == w[lf + 1])
        {
            res.push_back(w[lf]);
            res.push_back(w[lf + 1]);
            res.push_back(w[rf]);
        }
        else
        if (mid == w[rf])
        {
            res.push_back(w[lf]);
            res.push_back(w[rf]);
            res.push_back(w[lf + 1]);
        }
    }
    else
    if (rf == 4)
    {
        int mid = getMedian(w[lf], w[rf], w[rf + 1]);
        if (mid == w[rf])
        {
            res.push_back(w[lf]);
            res.push_back(w[rf]);
            res.push_back(w[rf + 1]);
        }
        else
        if (mid == w[rf + 1])
        {
            res.push_back(w[rf]);
            res.push_back(w[rf + 1]);
            res.push_back(w[lf]);
        }
        else
        if (mid == w[lf])
        {
            res.push_back(w[rf]);
            res.push_back(w[lf]);
            res.push_back(w[rf + 1]);
        }
    }

    for (int i = 0; i < res.size(); i ++)
        w[i] = res[i];
}

void orderCoins()
{
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};

    sort_range(0, 2, W);
    sort_range(3, 5, W);
    /**for (int i = 0; i < 6; i ++)
        cout << W[i] << " ";
    cout << endl;
    exit(0);*/
    merge_sort(W);

    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
    6 | void init(int T)
      |           ~~~~^
scales.cpp: In function 'void merge_sort(int*)':
scales.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < res.size(); i ++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 55.555556 / 100