제출 #890442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890442		amirhoseinfar1385	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	335 ms	1068 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=405;
int n,m;

int check(vector<int> a,int mid){
    vector<int>pors;
    for(int i=0;i<=mid;i++){
        pors.push_back(a[i]);
    }
    return Query(pors);
}

pair<vector<int>,vector<int>> upd(vector<int> a,int z,int ind){
    vector<int>retr,retl;
    for(int i=0;i<(int)a.size();i++){
        if(i<=ind){
            retl.push_back(a[i]);
        }
        else{
            retr.push_back(a[i]);
        }
    }
    vector<int>fake;
    while((int)retl.size()>0){
        int x=retl.back();
        retl.pop_back();
        vector<int>tof;
        tof=retl;
        for(auto y:fake){
            tof.push_back(y);
        }
        int zz=Query(tof);
        if(zz==z/2){
            retr.push_back(x);
        }
        else{
            fake.push_back(x);
        }
    }
    return make_pair(fake,retr);
}

void solve(vector<int>all){
    if((int)all.size()==n){
        Answer(all);
        return ;
    }
    int z=(int)all.size()/n;
    int low=0,high=(int)all.size()+1,mid;
    while(high-low>1){
        mid=(high+low)>>1;
        if(check(all,mid)<=z/2){
            low=mid;
        }
        else{
            high=mid;
        }
    }
    vector<int>l,r;
    pair<vector<int>,vector<int>>naaaa=upd(all,z,low);
    l=naaaa.first;
    r=naaaa.second;
    solve(l);
    solve(r);
}

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

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