oj.uz

Submission #158472

# Submission time Handle Problem Language Result Execution time Memory
158472 2019-10-17T09:20:20 Z davitmarg Scales (IOI15_scales) C++17
45.4545 / 100
 9 ms 380 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000000ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

#ifndef death
#include "scales.h"
#endif

#ifdef death

int getHeaviest(int a, int b, int c)
{
    cout << "? Heavy " << a << " " << b << " " << c << endl;
    int res;
    cin >> res;
    return res;
}

int getMedian(int a, int b, int c)
{
    cout << "? Median " << a << " " << b << " " << c << endl;
    int res;
    cin >> res;
    return res;
}

int getLightest(int a, int b, int c)
{
    cout << "? Light " << a << " " << b << " " << c << endl;
    int res;
    cin >> res;
    return res;
}

int getNextLightest(int a, int b, int c, int d)
{
    cout << "? Next " << a << " " << b << " " << c << " " << d << endl;
    int res;
    cin >> res;
    return res;
}

void answer(int *a)
{
    cout << "! ";
    for (int i = 0; i < 6; i++)
        cout << a[i] << " ";
    cout << endl;
}

#endif

int n = 6;

void init(int T)
{
    srand(5498659);
}

void orderCoins()
{
    vector<int> ind, l, r, ans;
    for (int i = 1; i <= n; i++)
        ind.PB(i);
    random_shuffle(all(ind));

    l.PB(getLightest(ind[0], ind[1], ind[2]));
    l.PB(getMedian(ind[0], ind[1], ind[2]));
    for (int i = 0; i < 3; i++)
        if (ind[i] != l[0] && ind[i] != l[1])
            l.PB(ind[i]);

    r.PB(getLightest(ind[3], ind[4], ind[5]));
    r.PB(getMedian(ind[3], ind[4], ind[5]));
    for (int i = 3; i < n; i++)
        if (ind[i] != r[0] && ind[i] != r[1])
            r.PB(ind[i]);

    reverse(all(l));
    reverse(all(r));
    ans.PB(getLightest(r.back(), l.back(), r[r.size() - 2]));
    if (ans.back() == r.back())
        r.pop_back();
    else
        l.pop_back();

    if (l.size() < r.size())
        swap(l, r);

    while (!l.empty() || !r.empty())
    {
        if (l.empty())
        {
            ans.PB(r.back());
            r.pop_back();
        }
        else if (r.empty())
        {
            ans.PB(l.back());
            l.pop_back();
        }
        else
        {
            int res = 0;
            res = getMedian(ans[0], r.back(), l.back());

            if (res != r.back())
            {
                if (l.size() != 1)
                {
                    if (l.size() == 3)
                    {
                        res = getNextLightest(l[0], l[1], l[2], r.back());
                        int x = l.back();
                        while (!l.empty() && (res == x || l.back() != res))
                        {
                            ans.PB(l.back());
                            l.pop_back();
                        }
                    }
                    else
                    {
                        res = getMedian(ans[0], r.back(), l[0]);
                        if (res == l[0])
                        {
                            while (!l.empty())
                            {
                                ans.PB(l.back());
                                l.pop_back();
                            }
                        }
                        else
                        {
                            ans.PB(l.back());
                            l.pop_back();
                        }
                    }
                }
                else
                {
                    ans.PB(l.back());
                    l.pop_back();
                }
            }
            ans.PB(r.back());
            r.pop_back();
        }
    }
    int ANS[6];
    for (int i = 0; i < n; i++)
        ANS[i] = ans[i];
    answer(ANS);
}

#ifdef death

int main()
{
    int T;
    cin >> T;
    init(T);
    while (T--)
    {
        orderCoins();
    }
    return 0;
}

#endif

/*

2 2 8
1 7

*/

Compilation message

scales.cpp: In function 'void init(int)':
scales.cpp:75:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^

Subtask #1
45.454545 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 256 KB Output is partially correct
2 Partially correct 9 ms 376 KB Output is partially correct
3 Partially correct 1 ms 256 KB Output is partially correct
4 Partially correct 2 ms 256 KB Output is partially correct
5 Partially correct 2 ms 252 KB Output is partially correct
6 Partially correct 2 ms 256 KB Output is partially correct
7 Partially correct 2 ms 252 KB Output is partially correct
8 Partially correct 3 ms 256 KB Output is partially correct
9 Partially correct 3 ms 256 KB Output is partially correct
10 Partially correct 2 ms 256 KB Output is partially correct
11 Partially correct 1 ms 128 KB Output is partially correct
12 Partially correct 2 ms 376 KB Output is partially correct
13 Partially correct 2 ms 256 KB Output is partially correct
14 Partially correct 2 ms 252 KB Output is partially correct
15 Partially correct 2 ms 376 KB Output is partially correct
16 Partially correct 2 ms 376 KB Output is partially correct
17 Partially correct 2 ms 376 KB Output is partially correct
18 Partially correct 2 ms 376 KB Output is partially correct
19 Partially correct 2 ms 380 KB Output is partially correct
20 Partially correct 2 ms 256 KB Output is partially correct
21 Partially correct 2 ms 376 KB Output is partially correct
22 Partially correct 2 ms 256 KB Output is partially correct
23 Partially correct 3 ms 376 KB Output is partially correct
24 Partially correct 2 ms 256 KB Output is partially correct
25 Partially correct 2 ms 376 KB Output is partially correct
26 Partially correct 2 ms 376 KB Output is partially correct
27 Partially correct 2 ms 256 KB Output is partially correct
28 Partially correct 2 ms 252 KB Output is partially correct
29 Partially correct 2 ms 252 KB Output is partially correct
30 Partially correct 2 ms 376 KB Output is partially correct
31 Partially correct 2 ms 376 KB Output is partially correct
32 Partially correct 2 ms 256 KB Output is partially correct
33 Partially correct 2 ms 256 KB Output is partially correct
34 Partially correct 2 ms 376 KB Output is partially correct
35 Partially correct 2 ms 256 KB Output is partially correct
36 Partially correct 0 ms 252 KB Output is partially correct
37 Partially correct 2 ms 256 KB Output is partially correct
38 Partially correct 2 ms 376 KB Output is partially correct
39 Partially correct 2 ms 256 KB Output is partially correct
40 Partially correct 1 ms 256 KB Output is partially correct