Submission #939248

#	Time	Username	Problem	Language	Result	Execution time	Memory
939248		Ice_man	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2367 ms	1136 KiB

dango3

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "dango3.h"

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


int n , m;

int query(vector <int> &e)
{
    vector <int> pom;

    int br[n * m + 5];
    for(int i = 0; i < n * m + 5; i++)
        br[i] = 0;

    for(int i : e)
        br[i]++;

    for(int i = 1; i <= n * m; i++)
        if(br[i] == 0)
            pom.pb(i);


    return m - Query(pom);
}



void Solve(int _n , int _m)
{
    n = _n;
    m = _m;

    vector <int> ans[m + 5];

    int l = 1;
    int r = m - 1;
    int in;

    for(int i = 1; i <= n * m; i++)
    {
        l = 1;
        r = m - 1;
        in = 0;

        while(l <= r)
        {
            int mid = (r - l) / 2 + l;
            ans[mid].pb(i);

            if(query(ans[mid]) > 1)
            {
                l = mid + 1;
                in = mid;
            }
            else
                r = mid - 1;

            ans[mid].pop_back();
        }
        ans[in + 1].pb(i);
    }

    for(int i = 1; i <= m; i++)
        Answer(ans[i]);


}

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