Submission #1319651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319651		Muhammad_Aneeq	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	758 ms	820 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
void Solve(int n, int m) 
{
    vector<vector<int>>ans;
    ans.push_back({n*m});
    vector<int>que;
    for (int i=1;i<=n*m-2;i++)
        que.push_back(i);
    int pre=m-ans.size();
    while (que.size())
    {
        pre=m-ans.size();
        int f=que.back();
        vector<int>inds;
        for (int i=0;i<ans.size();i++)
        {
            if (ans[i].size()!=n)
                inds.push_back(i);
        }
        int st=-2,en=inds.size();
        while (st+1<en)
        {
            int mid=(st+en)/2;
            vector<int>g=que;
            for (int j=0;j<=mid;j++)
            {
                for (auto k:ans[inds[j]])
                    g.push_back(k);
            }
            int f=Query(g);
            if (f==pre+mid+1)
                st=mid;
            else
                en=mid;
        }
        if (en==-1)
        {
            en=inds.size();
            inds.push_back(ans.size());
            ans.push_back({});
        }
        // cout<<inds[en]<<' '<<f+1<<' '<<pre<<endl;
        ans[inds[en]].push_back(f+1);
        que.pop_back();
    }
    for (auto& i:ans)
    {
        if (i.size()!=n)
            i.push_back(1);
    }
    for (auto i:ans)
        Answer(i);
}

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