Submission #972696

#	Time	Username	Problem	Language	Result	Execution time	Memory
972696		hotboy2703	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2216 ms	1112 KiB

dango3

#include "dango3.h"

#include <bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i))
#define sz(a) (ll((a).size()))
namespace {
    vector <ll> ans[26];
    mt19937_64 rng(69420);
    bool in[10010];
}
void f(){}
void Solve(int n,int m) {
    auto alldif = [&](vector <ll> x) -> bool{
        if (sz(x) < 2)return 1;
        for (auto y:x)in[y] = 1;
        vector <ll> tmp;
        for (ll i = 1;i <= n * m;i ++)(in[i]) ? f() :tmp.push_back(i);
        for (auto y:x)in[y] = 0;
//        cout<<"ALLDIF\n";
//        for (auto y:x)cout<<y<<' ';
//        cout<<'\n';
//        for (auto y:tmp)cout<<y<<' ';
//        cout<<'\n';
        return (Query(tmp)== m - 1);
    };
    for (ll i = 1;i <= n * m;i ++){
        ll l = 1;
        ll r = m;
        ll res;
        while (l <= r){
            ll mid = (l + r) >> 1;
            ans[mid].push_back(i);
//            cout<<"FIND "<<l<<' '<<r<<' '<<mid<<'\n';
            if (alldif(ans[mid])){
                res = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
            ans[mid].pop_back();
        }
//        cout<<"ANS "<< i<<' '<<res<<'\n';
        ans[res].push_back(i);
    }
//    for (ll i = 1;i <= m;i ++){for (auto x:ans[i])cout<<x<<' ';cout<<'\n';}
    for (ll i = 1;i <= m;i ++)Answer(ans[i]);
}

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