oj.uz

Submission #544671

# Submission time Handle Problem Language Result Execution time Memory
544671 2022-04-02T14:20:24 Z blue Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2362 ms 852 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include "dango3.h"
using namespace std;

namespace {

int variable_example = 1;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

int N, M;

}  // namespace	

int boolquery(vi& inset)
{
	vi qr;
	for(int i = 1; i <= N*M; i++)
		if(inset[i])
			qr.push_back(i);

	// cerr << "do query : ";
	// for(int i = 1; i <= N*M; i++) cerr << inset[i] << ' ';
	// 	cerr << '\n';

	// cerr << "query size = " << sz(qr) << '\n';

	return Query(qr);
}

void compute(vi lst)
{
	// cerr << "lst size = " << sz(lst) << '\n';
	int lists = sz(lst)/N;

	if(lists == 1) 
	{
		// cerr << "answering : ";
		// for(int k : lst) cerr << k << ' ';
		// 	cerr << '\n';
		Answer(lst);
	}
	else
	{
		// int lft = lists/2;

		vi trial(1+N*M, 0);
		for(int q : lst) trial[q] = 1;

		vi lftvec, rgtvec;
		for(int k : lst)
		{
			trial[k] = 0;
			if(boolquery(trial) >= lists/2)
			{
				// cerr << "pushing left\n";
				lftvec.push_back(k);
			}
			else
			{
				// cerr << "pushing right\n";
				trial[k] = 1;
				rgtvec.push_back(k);
			}
		}

		// cerr << "lftvec = ";
		// for(int v : lftvec) cerr << v << ' ';
		// 	cerr << '\n';
		// cerr << "\n\n\n";


		// if(sz(lst) == 15)
		{

			compute(lftvec);
			compute(rgtvec);
		}
	}
}		

void Solve(int N_, int M_)
{
	N = N_;
	M = M_;

	vi lst;
	for(int i = 1; i <= N*M; i++) lst.push_back(i);

	compute(lst);
}

Compilation message

dango3.cpp:13:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   13 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB Output is correct
2 Correct 18 ms 340 KB Output is correct
3 Correct 19 ms 340 KB Output is correct
4 Correct 19 ms 340 KB Output is correct
5 Correct 19 ms 380 KB Output is correct
6 Correct 20 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 588 KB Output is correct
2 Correct 563 ms 644 KB Output is correct
3 Correct 564 ms 584 KB Output is correct
4 Correct 565 ms 588 KB Output is correct
5 Correct 531 ms 492 KB Output is correct
6 Correct 554 ms 584 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 2287 ms 820 KB Output is correct
2 Correct 2273 ms 852 KB Output is correct
3 Correct 2254 ms 832 KB Output is correct
4 Correct 2362 ms 828 KB Output is correct
5 Correct 2252 ms 828 KB Output is correct
6 Correct 2256 ms 752 KB Output is correct