제출 #1247543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247543		Zbyszek99	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	211 ms	628 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

bool used[400*25+1];

void Solve(int n, int m) 
{   
    rep(i,m-1)
    {
        vi ans;
        vi cur;
        rep2(j,1,n*m) if(used[j] == 0) cur.pb(j);
        pii best = {1e9,-1};
        rep2(d,1,100)
        {
            best = min(best,{(__lg(d)+1)*n+(n*m-i*n+d-1)/d,d});
        }
        int d = best.ss;
        while(siz(ans) < n)
        {
            vi del;
            rep(k,min(d,siz(cur)))
            {
                del.pb(cur.back());
                cur.pop_back();
            }
            forall(it,ans) cur.pb(it);
            if(siz(cur) < n || Query(cur) == 0)
            {
                reverse(all(del));
                int l = 0;
                int r = siz(del)-1;
                int ans2 = -1;
                while(l <= r)
                {
                    if(ans2 == -1 && l == r)
                    {
                        ans2 = l;
                        break;
                    }
                    int mid = (l+r)/2;
                    rep(i,mid+1) cur.pb(del[i]);
                    int q = Query(cur);
                    rep(i,mid+1) cur.pop_back();
                    if(q >= 1)
                    {
                        ans2 = mid;
                        r = mid-1;
                    }
                    else
                    {
                        l = mid+1;
                    }
                }
                rep(i,siz(ans)) cur.pop_back();
                ans.pb(del[ans2]);
                rep(i,ans2) cur.pb(del[i]);
            } 
            else
            {
                rep(i,siz(ans)) cur.pop_back();
            }
        }
        Answer(ans);
        forall(it,ans) used[it] = 1;
    }
    vi ans;
    rep2(i,1,n*m) if(!used[i]) ans.pb(i);
    Answer(ans);
}

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