Submission #945250

#	Time	Username	Problem	Language	Result	Execution time	Memory
945250		socpite	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	380 ms	964 KiB

dango3

#include<bits/stdc++.h>
using namespace std;

int Query(const std::vector<int> &x);

void Answer(const std::vector<int> &a);

void dnc_solve(int N, int M, const vector<int> &a){
    if(M == 1){
        Answer(a);
        return;
    }
    vector<int> v1, v2;
    for(int i = 0; i < a.size(); i++){
        vector<int> nw = v1;
        for(int j = i + 1; j < a.size(); j++)nw.push_back(a[j]);
        if(Query(nw) < M/2)v1.push_back(a[i]);
        else v2.push_back(a[i]);
    }
    dnc_solve(N, M/2, v1);
    dnc_solve(N, (M+1)/2, v2);
}

void Solve(int N, int M) {
    vector<int> vec(N*M);
    iota(vec.begin(), vec.end(), 1);
    dnc_solve(N, M, vec);
}

Compilation message (stderr)

dango3.cpp: In function 'void dnc_solve(int, int, const std::vector<int>&)':
dango3.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
dango3.cpp:16:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int j = i + 1; j < a.size(); j++)nw.push_back(a[j]);
      |                            ~~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78