제출 #1076270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076270		Joshua_Andersson	저울 (IOI15_scales)	C++14	0 / 100	1 ms	604 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

#define DEB 1
int q1(const vi& items, int a, int b, int c)
{
    if (items[a] > items[b] && items[a] > items[c]) return a;
    if (items[b] > items[a] && items[b] > items[c]) return b;
    if (items[c] > items[b] && items[c] > items[a]) return c;
    
}
int q2(const vi& items, int a, int b, int c)
{
    if (items[a] < items[b] && items[a] < items[c]) return a;
    if (items[b] < items[a] && items[b] < items[c]) return b;
    if (items[c] < items[b] && items[c] < items[a]) return c;
}
int q3(const vi& items, int a, int b, int c)
{
    vector<p2> v;
    v.emplace_back(items[a], a);
    v.emplace_back(items[b], b);
    v.emplace_back(items[c], c);
    sort(all(v));
    return v[1].second;
}
int q4(const vi& items, int a, int b, int c, int d)
{
    vector<p2> heavier;
    if (items[a] > items[d]) heavier.emplace_back(items[a], a);
    if (items[b] > items[d]) heavier.emplace_back(items[b], b);
    if (items[c] > items[d]) heavier.emplace_back(items[c], c);
    if (sz(heavier))
    {
        sort(all(heavier));
        return heavier[0].second;
    }
    else
    {
        return q2(items, a, b, c);
    }
}

uniform_int_distribution<int> adist(0, 3);
uniform_int_distribution<int> ndist(0, 5);
mt19937 rng(rand());
pair<int, vi> getmove(const vvi& possible)
{
    int move = adist(rng);
    if (move == 0)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q1(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{0,a,b,c} };
    }
    if (move == 1)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q2(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{1,a,b,c} };
    }
    if (move == 2)
    {
        int a, b, c;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        vi s = { a,b,c };
        a = s[0];
        b = s[1];
        c = s[2];

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q3(p, a, b, c) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{2,a,b,c} };
    }
    else
    {
        int a, b, c, d;
        a = ndist(rng);
        b = ndist(rng);
        while (b == a) b = ndist(rng);
        c = ndist(rng);
        while (c == b || c == a) c = ndist(rng);
        d = ndist(rng);
        while (d == a || d == b || d == c) d = ndist(rng);
        vi s = { a,b,c, d };

        int tot = 0;
        rep(resp, 3)
        {
            int newsz = 0;
            repe(p, possible)
            {
                if (q4(p, a, b, c, d) == s[resp])
                {
                    newsz++;
                }
            }
            tot = max(tot, newsz);
        }
        return { tot,{3,a,b,c, d} };
    }
}

vvi filter(const vvi& possible, vi& bestquery)
{
    vvi newp;

    if (bestquery[0] == 0)
    {
        int resp = getHeaviest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q1(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 1)
    {
        int resp = getLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q2(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 2)
    {
        int resp = getMedian(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1) - 1;
        repe(p, possible)
        {
            if (q3(p, bestquery[1], bestquery[2], bestquery[3]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else if (bestquery[0] == 3)
    {
        int resp = getNextLightest(bestquery[1] + 1, bestquery[2] + 1, bestquery[3] + 1, bestquery[4] + 1) - 1;
        repe(p, possible)
        {
            if (q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]) == resp)
            {
                newp.push_back(p);
            }
        }
    }
    else assert(0);
    return newp;
}

vvi fakefilter(const vvi& possible, const vi& bestquery)
{
    vvi newp;


    rep(resp, 3)
    {
        vvi res;
        repe(p, possible)
        {
            int v;
            if (bestquery[0] == 0) v = q1(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 1) v = q2(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 2) v = q3(p, bestquery[1], bestquery[2], bestquery[3]);
            if (bestquery[0] == 3) v = q4(p, bestquery[1], bestquery[2], bestquery[3], bestquery[4]);
            if (v == bestquery[resp+1])
            {
                res.push_back(p);
            }
        }
        if (sz(res) > sz(newp)) newp = res;
    }
    

    return newp;
}

vi goals = { 240, 80, 28, 9, 3, 1 };
void rec(vvi possible, int d)
{
    if (sz(possible)==1)
    {
        cout << d << "\n";
        return;
    }
    rep(i, 3)
    {
        rep(a, 6)
        {
            rep(b, 6)
            {
                if (a == b) continue;
                rep(c, 6)
                {
                    if (c == b || c == a) continue;
                    vvi n = fakefilter(possible, vi({ i,a,b,c }));
                    if (sz(n)<=sz(possible)/3)
                    {
                        rec(n, d + 1);
                    }
                }
            }
        }
    }
}

void init(int T) {
    return;
#if !_LOCAL
    return;
#endif
    vvi possible;
    vi order = { 1,2,3,4,5,6 };
    do
    {
        possible.push_back(order);
    } while (next_permutation(order.begin(),order.end()));
    vvi queries = { { 0,4,5,2 },
        //tie(_, q2) = getmove(possible);
        { 2,3,0,1 },
        //tie(_, q3) = getmove(possible);
        { 3,0,5,2,1 },
        {0, 3, 1, 5},
        {2, 1, 2, 3},
        {3, 5, 0, 3, 4}
    };
    repe(q, queries) possible = fakefilter(possible, q);
    if (0)
    {

        rec(possible, 0);

    }
    
    auto start = chrono::high_resolution_clock::now();

    vvi bestquery;
    int bestval = 10000;
    //while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() < 500)
    rep(i, 1000000)
    {
        int _;
        vi q1, q2, q3;
        tie(_, q1) = getmove(possible);
        tie(_, q2) = getmove(possible);
        tie(_, q3) = getmove(possible);
        
        vvi res = fakefilter(possible, q1);
        res = fakefilter(res, q2);
        res = fakefilter(res, q3);
        if (sz(res)<bestval)
        {
            assert(sz(res));
            bestval = sz(res);
            bestquery = { q1,q2, q3};
            if (bestval<=1)
            {
                break;
            }
        }
    }
    cout << bestval << "\n";
    repe(q, bestquery)
    {
        repe(v, q) cout << v << " ";
        cout << "\n";
    }
}



void orderCoins() {

    vvi possible;
    vi order = { 1,2,3,4,5,6 };
    do
    {
        possible.push_back(order);
    } while (next_permutation(order.begin(), order.end()));


    vvi queries = { { 0,4,5,2 },
        { 2,3,0,1 },
        { 3,0,5,2,1 },
        {0, 3, 1, 5},
        {2, 1, 2, 3},
        {3, 5, 0, 3, 4}
    };
    repe(q, queries) possible = filter(possible, q);

    vi p = possible[0];
    int W[] = { 0,
                0, 
                0, 
                0, 
                0, 
                0};
    rep(i, 6) W[p[i]-1] = i + 1;
    answer(W);
}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:318:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  318 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
scales.cpp:290:15: warning: unused parameter 'T' [-Wunused-parameter]
  290 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int q1(const vi&, int, int, int)':
scales.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^
scales.cpp: In function 'int q2(const vi&, int, int, int)':
scales.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^
scales.cpp: In function 'vvi fakefilter(const vvi&, const vi&)':
scales.cpp:249:13: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  249 |             if (v == bestquery[resp+1])
      |             ^~

• Subtask 1: 0 / 100