oj.uz

Submission #971786

# Submission time Handle Problem Language Result Execution time Memory
971786 2024-04-29T09:34:13 Z 12345678 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2304 ms 1404 KB 
#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e4+5;

int m, mx;

int max_cardinality(vector<int> v)
{
    int d[nx];
    for (int i=1; i<=mx; i++) d[i]=1;
    for (auto x:v) d[x]=0;
    vector<int> qrs;
    for (int i=1; i<=mx; i++) if (d[i]) qrs.push_back(i);
    return m-Query(qrs);
}

void solve(int x, vector<int> v)
{
    //cout<<"size "<<x<<' '<<v.size()<<'\n';
    if (x==1) return Answer(v), void(); 
    vector<int> t, l, r;
    int k=x/2;
    for (int i=0; i<v.size(); i++)
    {
        t.push_back(v[i]);
        /*
        cout<<"query ";
        for (auto y:t) cout<<y<<' ';
        cout<<'\n';
        cout<<"result "<<max_cardinality(t)<<'\n';
        */
        if (max_cardinality(t)>k) t.pop_back(), r.push_back(v[i]);
        else l.push_back(v[i]);
    }
    solve(k, l);
    solve(x-k, r);
}

void Solve(int N, int M) {
    m=M;
    mx=N*M;
    vector<int> v;
    for (int i=1; i<=mx; i++) v.push_back(i);
    solve(M, v);
}

Compilation message

dango3.cpp: In function 'void solve(int, std::vector<int>)':
dango3.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0; i<v.size(); 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 348 KB Output is correct
5 Correct 1 ms 436 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 16 ms 440 KB Output is correct
2 Correct 19 ms 600 KB Output is correct
3 Correct 19 ms 600 KB Output is correct
4 Correct 17 ms 604 KB Output is correct
5 Correct 16 ms 592 KB Output is correct
6 Correct 16 ms 592 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 804 KB Output is correct
2 Correct 519 ms 1040 KB Output is correct
3 Correct 592 ms 804 KB Output is correct
4 Correct 575 ms 708 KB Output is correct
5 Correct 522 ms 800 KB Output is correct
6 Correct 513 ms 848 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 2106 ms 1112 KB Output is correct
2 Correct 2099 ms 1064 KB Output is correct
3 Correct 2287 ms 1192 KB Output is correct
4 Correct 2304 ms 1404 KB Output is correct
5 Correct 2040 ms 1068 KB Output is correct
6 Correct 2016 ms 1064 KB Output is correct