oj.uz

Submission #939248

# Submission time Handle Problem Language Result Execution time Memory
939248 2024-03-06T07:29:30 Z Ice_man Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2367 ms 1136 KB 
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "dango3.h"

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


int n , m;

int query(vector <int> &e)
{
    vector <int> pom;

    int br[n * m + 5];
    for(int i = 0; i < n * m + 5; i++)
        br[i] = 0;

    for(int i : e)
        br[i]++;

    for(int i = 1; i <= n * m; i++)
        if(br[i] == 0)
            pom.pb(i);


    return m - Query(pom);
}



void Solve(int _n , int _m)
{
    n = _n;
    m = _m;

    vector <int> ans[m + 5];

    int l = 1;
    int r = m - 1;
    int in;

    for(int i = 1; i <= n * m; i++)
    {
        l = 1;
        r = m - 1;
        in = 0;

        while(l <= r)
        {
            int mid = (r - l) / 2 + l;
            ans[mid].pb(i);

            if(query(ans[mid]) > 1)
            {
                l = mid + 1;
                in = mid;
            }
            else
                r = mid - 1;

            ans[mid].pop_back();
        }
        ans[in + 1].pb(i);
    }

    for(int i = 1; i <= m; i++)
        Answer(ans[i]);


}

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 600 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 17 ms 512 KB Output is correct
2 Correct 15 ms 348 KB Output is correct
3 Correct 16 ms 516 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 15 ms 348 KB Output is correct
6 Correct 15 ms 508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 596 KB Output is correct
2 Correct 496 ms 608 KB Output is correct
3 Correct 557 ms 636 KB Output is correct
4 Correct 557 ms 604 KB Output is correct
5 Correct 493 ms 868 KB Output is correct
6 Correct 500 ms 848 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1970 ms 948 KB Output is correct
2 Correct 2009 ms 968 KB Output is correct
3 Correct 2367 ms 1136 KB Output is correct
4 Correct 2239 ms 1008 KB Output is correct
5 Correct 1954 ms 952 KB Output is correct
6 Correct 1954 ms 848 KB Output is correct