Submission #905949

#	Time	Username	Problem	Language	Result	Execution time	Memory
905949		minhnhatnoe	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	1842 ms	1156 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


namespace{
    int n, m;
    vector<vector<int>> a;
}

int query_max(const vector<vector<int>> &a, const vector<int> &t){
    vector<bool> s(n * m, 1);
    for (const vector<int> &h: a){
        for (int v: h){
            s[v] = 0;
        }
    }
    for (int v: t) s[v] = 0;

    vector<int> q;
    for (int i=0; i<s.size(); i++){
        if (s[i]) q.push_back(i+1);
    }
    return m - Query(q);
}

void insert_into(int l, int r, int pos){
    if (l == r){
        a[l].push_back(pos);
        return;
    }
    int m = (l + r)>>1;
    if (query_max({a.begin() + l, a.begin() + m + 1}, {pos}) <= m - l + 1){
        insert_into(l, m, pos);
    }
    else{
        insert_into(m+1, r, pos);
    }
}
void Solve(int N, int M){
    n = N, m = M;
    a.resize(m);
    for (int i=0; i<n*m; i++){
        insert_into(0, m-1, i);
    }
    for (int i=0; i<m; i++){
        for (int &v: a[i]) v++;
        Answer(a[i]);
    }
}

Compilation message (stderr)

dango3.cpp: In function 'int query_max(const std::vector<std::vector<int> >&, const std::vector<int>&)':
dango3.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0; i<s.size(); i++){
      |                   ~^~~~~~~~~

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