Submission #971786

#	Time	Username	Problem	Language	Result	Execution time	Memory
971786		12345678	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2304 ms	1404 KiB

dango3

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

using namespace std;

const int nx=1e4+5;

int m, mx;

int max_cardinality(vector<int> v)
{
    int d[nx];
    for (int i=1; i<=mx; i++) d[i]=1;
    for (auto x:v) d[x]=0;
    vector<int> qrs;
    for (int i=1; i<=mx; i++) if (d[i]) qrs.push_back(i);
    return m-Query(qrs);
}

void solve(int x, vector<int> v)
{
    //cout<<"size "<<x<<' '<<v.size()<<'\n';
    if (x==1) return Answer(v), void(); 
    vector<int> t, l, r;
    int k=x/2;
    for (int i=0; i<v.size(); i++)
    {
        t.push_back(v[i]);
        /*
        cout<<"query ";
        for (auto y:t) cout<<y<<' ';
        cout<<'\n';
        cout<<"result "<<max_cardinality(t)<<'\n';
        */
        if (max_cardinality(t)>k) t.pop_back(), r.push_back(v[i]);
        else l.push_back(v[i]);
    }
    solve(k, l);
    solve(x-k, r);
}

void Solve(int N, int M) {
    m=M;
    mx=N*M;
    vector<int> v;
    for (int i=1; i<=mx; i++) v.push_back(i);
    solve(M, v);
}

Compilation message (stderr)

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

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