제출 #1170360

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

minerals

#include "minerals.h"

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

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

int N;

mt19937 gen(234678);

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;
    int ilea = 0, ileb = 0;
    for (int i = 0; i < N; i ++) {
        if (ilea == N/2) {
            b.pb(v[i]);
            ileb ++;
            continue;
        }
        if (ileb == N/2) {
            a.pb(v[i]);
            ilea ++;
            continue;
        }
        int x = Query(v[i]);
        if (x == stare) {
            a.pb(v[i]);
            ilea ++;
        } else {
            b.pb(v[i]);
            ileb ++;
        }
        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;
    }

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

    int roz1 = m/2, roz2 = m - roz1;

    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) {

    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: 0 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10