oj.uz

Submission #940758

# Submission time Handle Problem Language Result Execution time Memory
940758 2024-03-07T15:16:19 Z PVM_pvm Super Dango Maker (JOI22_dango3) C++17
100 / 100
 135 ms 1104 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
void boqn(vector<int> pozicii, int cn, int cm)
{
    random_shuffle(pozicii.begin(),pozicii.end());
    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]);
        int qu=Query(zaqu);
        if (qu<cm/2) l=mid;
        else r=mid;
    }
    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);
        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 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 0 ms 344 KB Output is correct
6 Correct 0 ms 344 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 608 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 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 30 ms 676 KB Output is correct
2 Correct 30 ms 604 KB Output is correct
3 Correct 32 ms 604 KB Output is correct
4 Correct 29 ms 604 KB Output is correct
5 Correct 33 ms 652 KB Output is correct
6 Correct 32 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 612 KB Output is correct
2 Correct 132 ms 800 KB Output is correct
3 Correct 125 ms 708 KB Output is correct
4 Correct 135 ms 1104 KB Output is correct
5 Correct 127 ms 848 KB Output is correct
6 Correct 131 ms 756 KB Output is correct