oj.uz

Submission #759330

# Submission time Handle Problem Language Result Execution time Memory
759330 2023-06-16T07:21:14 Z ymm Super Dango Maker (JOI22_dango3) C++17
100 / 100
 234 ms 1160 KB 
#include "dango3.h"

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

mt19937_64 rd(time(0));

void Do(vector<int> vec, int n, int m)
{
	if (m == 0)
		return;
	int cnt = min(m, 4);
	vector<int> q;
	for (;;) {
		shuffle(vec.begin(), vec.end(), rd);
		q = vector<int>(vec.begin(), vec.begin() + n*cnt);
		if (Query(q))
			break;
	}
	vector<int> idx;
	LoopR (i,0,q.size()) {
		int tmp = q[i];
		swap(q[i], q.back());
		q.pop_back();
		if (Query(q) == 0) {
			q.push_back(tmp);
			idx.push_back(i);
		}
	}
	for (int &i : idx) {
		int tmp = vec[i];
		swap(vec[i], vec.back());
		vec.pop_back();
		i = tmp;
	}
	Answer(idx);
	Do(vec, n, m-1);
}

}  // namespace

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

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 744 KB Output is correct
2 Correct 24 ms 720 KB Output is correct
3 Correct 23 ms 680 KB Output is correct
4 Correct 24 ms 648 KB Output is correct
5 Correct 24 ms 696 KB Output is correct
6 Correct 31 ms 776 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 1160 KB Output is correct
2 Correct 211 ms 1148 KB Output is correct
3 Correct 234 ms 1112 KB Output is correct
4 Correct 229 ms 1156 KB Output is correct
5 Correct 205 ms 1104 KB Output is correct
6 Correct 186 ms 1148 KB Output is correct