oj.uz

Submission #995620

# Submission time Handle Problem Language Result Execution time Memory
995620 2024-06-09T13:17:29 Z onbert Super Dango Maker (JOI22_dango3) C++17
100 / 100
 275 ms 944 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

void Solve(int32_t n, int32_t m) {
    vector<pair<int, vector<int32_t>>> v = {{m, {}}};
    for (int i=1;i<=n*m;i++) v[0].second.push_back(i);
    for (int i=0;i<v.size();i++) {
        auto [sz, a] = v[i];
        if (sz==1) {
            // cout << "ANS\n";
            // for (int j:a) cout << j << " "; cout << endl;
            Answer(a);
            continue;
        }
        int mid = sz/2;
        v.push_back({(sz+1)/2, {}});
        vector<int32_t> A = a;
        for (int j:a) {
            A.erase(find(A.begin(), A.end(), j));
            if (Query(A) >= mid) v.back().second.push_back(j);
            else A.push_back(j);
        }
        v.push_back({mid, A});
    }
}

Compilation message

dango3.cpp: In function 'void Solve(int32_t, int32_t)':
dango3.cpp:9:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0;i<v.size();i++) {
      |                  ~^~~~~~~~~

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 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 628 KB Output is correct
2 Correct 55 ms 604 KB Output is correct
3 Correct 70 ms 600 KB Output is correct
4 Correct 69 ms 600 KB Output is correct
5 Correct 56 ms 604 KB Output is correct
6 Correct 55 ms 620 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 848 KB Output is correct
2 Correct 217 ms 856 KB Output is correct
3 Correct 275 ms 852 KB Output is correct
4 Correct 273 ms 944 KB Output is correct
5 Correct 213 ms 752 KB Output is correct
6 Correct 233 ms 732 KB Output is correct