oj.uz

Submission #951616

# Submission time Handle Problem Language Result Execution time Memory
951616 2024-03-22T07:37:20 Z LittleOrange Super Dango Maker (JOI22_dango3) C++17
100 / 100
 251 ms 724 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 568 KB Output is correct
2 Correct 44 ms 344 KB Output is correct
3 Correct 53 ms 348 KB Output is correct
4 Correct 57 ms 600 KB Output is correct
5 Correct 47 ms 600 KB Output is correct
6 Correct 46 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 604 KB Output is correct
2 Correct 201 ms 700 KB Output is correct
3 Correct 176 ms 604 KB Output is correct
4 Correct 204 ms 724 KB Output is correct
5 Correct 200 ms 604 KB Output is correct
6 Correct 251 ms 696 KB Output is correct