oj.uz

Submission #890441

# Submission time Handle Problem Language Result Execution time Memory
890441 2023-12-21T09:04:16 Z amirhoseinfar1385 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 331 ms 1132 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 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 440 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 704 KB Output is correct
2 Correct 51 ms 652 KB Output is correct
3 Correct 83 ms 848 KB Output is correct
4 Correct 81 ms 700 KB Output is correct
5 Correct 36 ms 604 KB Output is correct
6 Correct 35 ms 640 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 884 KB Output is correct
2 Correct 200 ms 800 KB Output is correct
3 Correct 331 ms 896 KB Output is correct
4 Correct 327 ms 908 KB Output is correct
5 Correct 133 ms 864 KB Output is correct
6 Correct 142 ms 1132 KB Output is correct