Submission #727386

#	Time	Username	Problem	Language	Result	Execution time	Memory
727386		Boycl07	Scales (IOI15_scales)	C++17	0 / 100	1 ms	340 KiB

scales

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

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
const int LIM = 721;

int p[7], pos[LIM][7], barr[LIM], nx[LIM], n, arr[LIM][7];

int find_nx(int x)
{
	if(!barr[nx[x]]) return nx[x];
	return nx[x] = find_nx(nx[x]);
}

void init(int T)
{
	int idx = 0;
	nx[0] = 1;
	rep(i, 6) p[i] = i;
	do
	{
		++idx;
		rep(i, 6) pos[idx][p[i]] = i;
		nx[idx] = idx + 1;
		rep(i, 6) arr[idx][i] = p[i];
	} while(next_permutation(p + 1, p + 1 + 6));
}

int w[6];

struct condition {
    int type;
    int a, b, c, d;
    int res;
    condition(){}
    condition(int type_, int a_, int b_, int c_) : type(type_), a(a_), b(b_), c(c_){}
    condition(int type_, int a_, int b_, int c_, int d_) : type(type_), a(a_), b(b_), c(c_), d(d_){}
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<condition> q;

void update()
{
    auto e = q.back();
    int type = e.type;
    int a = e.a, b = e.b, c = e.c, d = e.d;
    if(type == 0)
        e.res = getLightest(a, b, c);
    else  if(type == 1)
        e.res = getMedian(a, b, c);
    else  if(type == 2)
        e.res = getHeaviest(a, b, c);
    else  e.res = getNextLightest(a, b, c, d);
    q.back().res = e.res;
}

int tmp[3];

bool check(int idx)
{

    for(auto e : q)
    {
        int type = e.type;
        int a = e.a, b = e.b, c = e.c, res = e.res;
        tmp[0] = a;
        tmp[1] = b;
        tmp[2] = c;
        sort(tmp, tmp + 3, [&idx](int x, int y) {
             return pos[idx][x] < pos[idx][y];
        });
        a = tmp[0];
        b = tmp[1];
        c = tmp[2];
//        cout << idx << endl;
//        cout << pos[idx][a] << " " << pos[idx][b] << " " << pos[idx][c] << endl;
//        cout << type << " " << a << " " << b << " " << c << endl;
//        cout << res << endl;
        if(type != 3)
        {

            if(type == 0)
            {
                if(res != a) return 0;
            }
            else if(type == 1)
            {
                if(res != b) return 0;
            }
            else
            {
                if(res != c) return 0;
            }
        }
        else
        {
            int d = e.d;
            if(pos[d] < pos[a])
            {
                if(res != a) return 0;
            }
            if(pos[d] < pos[b])
            {
                if(res != b) return 0;
            }
            if(res != c) return 0;
        }
    }
    return 1;
}

int randint(int l, int r)
{
    return rng() % (r - l + 1) + l;
}

void orderCoins()
{
    int cnt = 720;
    rep(i, 720) barr[i] = 0, nx[i] = i + 1;
    q.clear();
    rep(a, 4)
    forn(b, a + 1, 5)
    forn(c, b + 1, 6)
    {
//        q.push_back(condition(0, a, b, c));update();
        //q.push_back(condition(1, a, b, c));update();
        //q.push_back(condition(2, a, b, c));update();
//        forn(d, 1, 6) if(d != a && d != b && d != c) q.push_back(condition(3, a, b, c, d));update();
        q.push_back(condition(0, a, b, c));update();
        //cout << q.size() << endl;
        //out << q.back().res << endl;

        int idx = find_nx(0);
        for(; idx <= 720; idx = find_nx(idx))
        {
            if(!check(idx)) --cnt, barr[idx] = 1;
        }
        if(cnt == 1)
        {
            int idx = find_nx(0);
            rep(i, 6) w[i - 1] = arr[idx][i];
            answer(w);
            return;
        }
    }
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:21:15: warning: unused parameter 'T' [-Wunused-parameter]
   21 | void init(int T)
      |           ~~~~^
scales.cpp: In function 'int randint(int, int)':
scales.cpp:122:32: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  122 |     return rng() % (r - l + 1) + l;
      |            ~~~~~~~~~~~~~~~~~~~~^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:149:17: warning: declaration of 'idx' shadows a previous local [-Wshadow]
  149 |             int idx = find_nx(0);
      |                 ^~~
scales.cpp:142:13: note: shadowed declaration is here
  142 |         int idx = find_nx(0);
      |             ^~~

• Subtask 1: 0 / 100