oj.uz

Submission #940718

# Submission time Handle Problem Language Result Execution time Memory
940718 2024-03-07T14:08:20 Z PVM_pvm Super Dango Maker (JOI22_dango3) C++17
100 / 100
 298 ms 1108 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
void boqn(vector<int> pozicii, int cn, int cm)
{
    /*cout<<"davam: "<<cn<<" "<<cm<<"\n";
    for (int q=0;q<pozicii.size();q++) cout<<pozicii[q]<<" ";
    cout<<"\n";*/
    if (cm==1)
    {
        Answer(pozicii);
        return;
    }
    int l=0,r=cn*cm;
        vector<int> zaqu;
    while (l<r-1)
    {
        int mid=(l+r)/2;
        zaqu.clear();
        for (int q=0;q<=mid;q++) zaqu.push_back(pozicii[q]);
        /*for (int q=0;q<zaqu.size();q++) cout<<zaqu[q]<<" ";
        cout<<"\n";*/
        int qu=Query(zaqu);
        //cout<<l<<" "<<mid<<" "<<r<<" "<<qu<<"\n";
        if (qu<cm/2) l=mid;
        else r=mid;
    }
    //cout<<r<<"\n";
    vector<int> pyrvo,vtoro;
    for (int q=0;q<=r;q++) pyrvo.push_back(pozicii[q]);
    for (int q=r+1;q<cn*cm;q++) vtoro.push_back(pozicii[q]);
    for (int q=r-1;q>=0;q--)
    {
        int poq=pyrvo[q];
        swap(pyrvo[pyrvo.size()-1],pyrvo[q]);
        pyrvo.pop_back();
        int qu=Query(pyrvo);
        //cout<<"mahnah "<<poq<<" "<<" i stana "<<qu<<"\n";
        if (qu<cm/2)
        {
            pyrvo.push_back(poq);
            swap(pyrvo[pyrvo.size()-1],pyrvo[q]);
        }
        else
        {
            vtoro.push_back(poq);
        }
    }
    boqn(pyrvo,cn,cm/2);
    boqn(vtoro,cn,cm-cm/2);
}
void Solve(int N, int M) {
    n=N;
    m=M;
    vector<int> og;
    for (int q=1;q<=n*m;q++) og.push_back(q);
    boqn(og,n,m);
}

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 436 KB Output is correct
3 Correct 0 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 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 512 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 600 KB Output is correct
2 Correct 36 ms 604 KB Output is correct
3 Correct 63 ms 716 KB Output is correct
4 Correct 66 ms 604 KB Output is correct
5 Correct 22 ms 600 KB Output is correct
6 Correct 22 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 784 KB Output is correct
2 Correct 151 ms 900 KB Output is correct
3 Correct 256 ms 920 KB Output is correct
4 Correct 298 ms 1108 KB Output is correct
5 Correct 88 ms 1008 KB Output is correct
6 Correct 81 ms 756 KB Output is correct