제출 #1170373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170373		anteknne	Minerals (JOI19_minerals)	C++20	100 / 100	40 ms	4376 KiB

minerals

#include "minerals.h"

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

typedef long double ld;

#define pb push_back
#define st first
#define nd second
#define debug false

mt19937 gen(234678);
uniform_int_distribution<int> dist(45, 55);

const ld fi = 1.618;

pair<vector<int>, vector<int>> szykuj (vector<int> v, int N) {
    shuffle(v.begin(), v.end(), gen);
    vector<int> a, b;
    a.clear();
    b.clear();
    int stare = -1;
    for (int i = 0; i < N; i ++) {
        int x = Query(v[i]);
        if (x == stare) {
            a.pb(v[i]);
        } else {
            b.pb(v[i]);
        }
        stare = x;
    }

    return (make_pair(a, b));
}

void dziel (vector<int> v1, vector<int> v2, int ile1) {

    shuffle(v1.begin(), v1.end(), gen);
    shuffle(v2.begin(), v2.end(), gen);

    if (debug) {
        cout << "v1 i v2" << ": " << "\n";
        for (auto x : v1) {
            cout << x << " ";
        }
        cout << "\n";
        for (auto x : v2) {
            cout << x << " ";
        }
        cout << "\n";
    }

    if (debug) {
        cout << "ile1: " << ile1 << "\n";
    }

    int m = int(v1.size());

    if (m == 1) {
        Answer(v1[0], v2[0]);
        return;
    }

    if (m == 0) {
        return;
    }

    vector<int> a1, b1, a2, b2;
    a1.clear(); b1.clear(); a2.clear(); b2.clear();

    //int roz1 = m * (ld(dist(gen))/100.0), roz2 = m - roz1;
    int roz2 = (ld(m) * fi)/ (1.0 + fi), roz1 = m - roz2;

    int stare = -1;
    for (int i = 0; i < roz1; i ++) {
        stare = Query(v1[i]);
        a1.pb(v1[i]);
    }
    for (int i = roz1; i < m; i ++) {
        a2.pb(v1[i]);
    }

    int el1 = 0, el2 = 0;
    for (int i = 0; i < m; i ++) {
        if (el1 == roz1) {
            b2.pb(v2[i]);
            el2 ++;
            continue;
        }
        if (el2 == roz2) {
            b1.pb(v2[i]);
            el1 ++;
            continue;
        }

        int x = Query(v2[i]);
        if (ile1 == 0) {
            if (x == stare) {
                b1.pb(v2[i]);
                el1 ++;
            } else {
                b2.pb(v2[i]);
                el2 ++;
            }
        }
        if (ile1 == 1) {
            if (x == stare) {
                b2.pb(v2[i]);
                el2 ++;
            } else {
                b1.pb(v2[i]);
                el1 ++;
            }
        }

        stare = x;
    }

    if (debug) {
        cout << "a1 i b1" << ": " << "\n";
        for (auto x : a1) {
            cout << x << " ";
        }
        cout << "\n";
        for (auto x : b1) {
            cout << x << " ";
        }
        cout << "\n";
        cout << "a2 i b2" << ": " << "\n";
        for (auto x : a2) {
            cout << x << " ";
        }
        cout << "\n";
        for (auto x : b2) {
            cout << x << " ";
        }
        cout << "\n";
    }

    dziel(a1, b1, ile1 ^ 1);
    dziel(a2, b2, ile1);

}

void Solve(int n) {

    int N = 2 * n;
    vector<int> v = {};
    for (int i = 1; i <= N; i ++) {
        v.pb(i);
    }

    pair<vector<int>, vector<int>> podzielone = szykuj(v, N);

    dziel(podzielone.st, podzielone.nd, 1);

}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10