oj.uz

Submission #905949

# Submission time Handle Problem Language Result Execution time Memory
905949 2024-01-13T07:41:31 Z minhnhatnoe Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1842 ms 1156 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


namespace{
    int n, m;
    vector<vector<int>> a;
}

int query_max(const vector<vector<int>> &a, const vector<int> &t){
    vector<bool> s(n * m, 1);
    for (const vector<int> &h: a){
        for (int v: h){
            s[v] = 0;
        }
    }
    for (int v: t) s[v] = 0;

    vector<int> q;
    for (int i=0; i<s.size(); i++){
        if (s[i]) q.push_back(i+1);
    }
    return m - Query(q);
}

void insert_into(int l, int r, int pos){
    if (l == r){
        a[l].push_back(pos);
        return;
    }
    int m = (l + r)>>1;
    if (query_max({a.begin() + l, a.begin() + m + 1}, {pos}) <= m - l + 1){
        insert_into(l, m, pos);
    }
    else{
        insert_into(m+1, r, pos);
    }
}
void Solve(int N, int M){
    n = N, m = M;
    a.resize(m);
    for (int i=0; i<n*m; i++){
        insert_into(0, m-1, i);
    }
    for (int i=0; i<m; i++){
        for (int &v: a[i]) v++;
        Answer(a[i]);
    }
}

Compilation message

dango3.cpp: In function 'int query_max(const std::vector<std::vector<int> >&, const std::vector<int>&)':
dango3.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0; i<s.size(); i++){
      |                   ~^~~~~~~~~

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 1 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 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 344 KB Output is correct
2 Correct 14 ms 508 KB Output is correct
3 Correct 13 ms 344 KB Output is correct
4 Correct 14 ms 348 KB Output is correct
5 Correct 13 ms 344 KB Output is correct
6 Correct 16 ms 344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 580 KB Output is correct
2 Correct 453 ms 852 KB Output is correct
3 Correct 480 ms 568 KB Output is correct
4 Correct 455 ms 952 KB Output is correct
5 Correct 431 ms 840 KB Output is correct
6 Correct 430 ms 588 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1770 ms 928 KB Output is correct
2 Correct 1842 ms 920 KB Output is correct
3 Correct 1751 ms 972 KB Output is correct
4 Correct 1674 ms 1156 KB Output is correct
5 Correct 1828 ms 1052 KB Output is correct
6 Correct 1703 ms 832 KB Output is correct