Submission #949511

#	Time	Username	Problem	Language	Result	Execution time	Memory
949511		alextodoran	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	492 ms	1104 KiB

dango3

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

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

using namespace std;

typedef long long ll;

int Query (const vector <int> &x);
void Answer (const vector <int> &a);

int n, m;

void solve (vector <int> v) {
    int cnt = (int) v.size();
    int k = cnt / n;
    if (k == 1) {
        for (int &i : v) {
            i++;
        }
        Answer(v);
        return;
    }
    k /= 2;
    bool in[n * m]; fill(in, in + n * m, true);
    for (int i : v) {
        in[i] = false;
        vector <int> x;
        for (int j : v) {
            if (in[j] == true) {
                x.push_back(j + 1);
            }
        }
        if (Query(x) < k) {
            in[i] = true;
        }
    }
    vector <int> split[2];
    for (int i : v) {
        split[in[i]].push_back(i);
    }
    solve(split[0]);
    solve(split[1]);
}

void Solve (int N, int M) {
    n = N; m = M;
    vector <int> v(n * m);
    iota(v.begin(), v.end(), 0);
    solve(v);
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78