oj.uz

Submission #544947

# Submission time Handle Problem Language Result Execution time Memory
544947 2022-04-03T08:00:35 Z cig32 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 4139 ms 644 KB 
#include "dango3.h"
#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
// #define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;
 
namespace {
 
int variable_example = 1;
 
}  // namespace
 
vector<int> dk;
vector<int> pre;
int n, m;
vector<int> sure[35];
bool har[10005];
int ask(int k, int l, int r) {
    // cerr << k << ' ' << l << ' ' << r << '\n';
    vector<int> t;
    for(int i = 1; i <= n * m; i++) har[i] = true;
    for(int x = l; x <= r; x++) {
        for(auto y: sure[x]) har[y] = false;
    }
    har[k] = false;
    for(int i = 1; i <= n * m; i++) if(har[i]) t.pb(i);
    return Query(t);
}
 
void Solve(int N, int M) {
    n = N, m = M;
 
    for(int i = 1; i <= n * m; i++) {
        int l = 0, r = m - 1;
        while(l < r) {
            int mid = ((l + r) >> 1);
            if(ask(i, l, mid) < m - (mid - l + 1)) l = mid + 1;
            else r = mid;
        }
        sure[l].pb(i);
    }
 
    for(int i = 0; i < m; i++) Answer(sure[i]);
    // return;
 
    // sure[n - 1] = dk;
    // vector<int> ans;
    // for(int i = 0; i < m; i++) {
    //     ans.clear();
    //     for(int j = 0; j < n; j++) {
    //         ans.pb(sure[j][i]);
    //     }
    //     Answer(ans);
    // }
    return;
}

Compilation message

dango3.cpp:14:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   14 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 340 KB Output is correct
2 Correct 27 ms 340 KB Output is correct
3 Correct 28 ms 372 KB Output is correct
4 Correct 33 ms 372 KB Output is correct
5 Correct 32 ms 340 KB Output is correct
6 Correct 31 ms 352 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 560 KB Output is correct
2 Correct 983 ms 456 KB Output is correct
3 Correct 987 ms 564 KB Output is correct
4 Correct 984 ms 576 KB Output is correct
5 Correct 997 ms 576 KB Output is correct
6 Correct 1006 ms 460 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 3952 ms 552 KB Output is correct
2 Correct 4124 ms 548 KB Output is correct
3 Correct 3980 ms 580 KB Output is correct
4 Correct 4139 ms 644 KB Output is correct
5 Correct 3731 ms 624 KB Output is correct
6 Correct 3864 ms 616 KB Output is correct