Submission #1170349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170349		anteknne	Minerals (JOI19_minerals)	C++20	80 / 100	24 ms	3624 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;

pair<vector<int>, vector<int>> szykuj (vector<int> v, int N) {
    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) {
    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;

    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]);
    }


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

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