oj.uz

Submission #949511

# Submission time Handle Problem Language Result Execution time Memory
949511 2024-03-19T10:03:56 Z alextodoran Super Dango Maker (JOI22_dango3) C++17
100 / 100
 492 ms 1104 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 600 KB Output is correct
2 Correct 108 ms 604 KB Output is correct
3 Correct 123 ms 600 KB Output is correct
4 Correct 125 ms 600 KB Output is correct
5 Correct 99 ms 604 KB Output is correct
6 Correct 99 ms 628 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 600 KB Output is correct
2 Correct 417 ms 1104 KB Output is correct
3 Correct 492 ms 736 KB Output is correct
4 Correct 471 ms 600 KB Output is correct
5 Correct 401 ms 844 KB Output is correct
6 Correct 382 ms 840 KB Output is correct