Submission #951616

#	Time	Username	Problem	Language	Result	Execution time	Memory
951616		LittleOrange	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	251 ms	724 KiB

dango3

#include "dango3.h"

#include <vector>
#include<bits/stdc++.h>

namespace {
    int variable_example = 1;
    using namespace std;
    using ll = int;
}  // namespace

void Solve(int N, int M) {
    ll nm = N*M;
    ll n = N;
    vector<ll> a(nm,1);
    mt19937_64 mt(random_device{}());
    for(ll round = 0;round<M;round++){
        vector<ll> b;
        for(ll i = 0;i<nm;i++) if(a[i])b.push_back(i+1);
        shuffle(b.begin(),b.end(),mt);
        if (round==M-1){
            Answer(b);
            return;
        }
        ll l = n,r=b.size();
        while(l<r){
            ll m = l+r>>1;
            vector<ll> c;
            for(ll i = 0;i<m;i++) c.push_back(b[i]);
            if(Query(c)>=1){
                r = m;
            }else{
                l = m+1;
            }
        }
        vector<ll> choose(l,1);
        ll chcnt = l;
        for(ll i = 0;i<l&&chcnt>n;i++){
            choose[i] = 0;
            vector<ll> c;
            for(ll i = 0;i<l;i++) if(choose[i])c.push_back(b[i]);
            if(Query(c)==0){
                choose[i] = 1;
            }else{
                chcnt--;
            }
        }
        vector<ll> out;
        for(ll i = 0;i<l;i++) if(choose[i]){
            out.push_back(b[i]);
            a[b[i]-1] = 0;
        }
        Answer(out);
    }
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             ll m = l+r>>1;
      |                    ~^~
dango3.cpp: At global scope:
dango3.cpp:7:9: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    7 |     int variable_example = 1;
      |         ^~~~~~~~~~~~~~~~

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