oj.uz

Submission #890443

# Submission time Handle Problem Language Result Execution time Memory
890443 2023-12-21T09:07:41 Z amirhoseinfar1385 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 327 ms 1056 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 4 ms 604 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 708 KB Output is correct
2 Correct 50 ms 604 KB Output is correct
3 Correct 82 ms 696 KB Output is correct
4 Correct 112 ms 904 KB Output is correct
5 Correct 35 ms 600 KB Output is correct
6 Correct 36 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 884 KB Output is correct
2 Correct 265 ms 824 KB Output is correct
3 Correct 316 ms 880 KB Output is correct
4 Correct 327 ms 1056 KB Output is correct
5 Correct 134 ms 844 KB Output is correct
6 Correct 127 ms 848 KB Output is correct