oj.uz

Submission #951688

# Submission time Handle Problem Language Result Execution time Memory
951688 2024-03-22T10:37:21 Z GrandTiger1729 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 173 ms 856 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

void Solve(int n, int m)
{
	vector<int> idx(n * m);
	iota(idx.begin(), idx.end(), 1);
	vector<vector<int>> ans;
	while (idx.size())
	{
		shuffle(idx.begin(), idx.end(), mt19937(time(0)));
		int rr = -1;
		{
			int l = 0, r = idx.size();
			while (l < r - 1)
			{
				int mid = (l + r) / 2;
				vector<int> qry;
				for (int i = 0; i < mid; i++)
				{
					qry.push_back(idx[i]);
				}
				int res = Query(qry);
				(res == 0 ? l : r) = mid;
			}
			rr = l;
		}
		vector<int> cur, idx2;
		cur.push_back(idx[rr]);
		for (int i = rr - 1; i >= 0; i--)
		{
			vector<int> qry = cur;
			for (int j = 0; j < i; j++)
			{
				qry.push_back(idx[j]);
			}
			int res = Query(qry);
			(res == 0 ? cur : idx2).push_back(idx[i]);
		}
		ans.push_back(cur);
		for (int i = rr + 1; i < idx.size(); i++)
		{
			idx2.push_back(idx[i]);
		}
		swap(idx, idx2);
	}
	for (int i = 0; i < m; i++)
	{
		Answer(ans[i]);
	}
}

Compilation message

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = rr + 1; i < idx.size(); i++)
      |                        ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 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 3 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 448 KB Output is correct
2 Correct 45 ms 604 KB Output is correct
3 Correct 39 ms 856 KB Output is correct
4 Correct 34 ms 600 KB Output is correct
5 Correct 39 ms 604 KB Output is correct
6 Correct 38 ms 664 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 792 KB Output is correct
2 Correct 163 ms 752 KB Output is correct
3 Correct 138 ms 800 KB Output is correct
4 Correct 157 ms 760 KB Output is correct
5 Correct 162 ms 660 KB Output is correct
6 Correct 149 ms 604 KB Output is correct