/* Im the best and i work like that */
#pragma GCC optimize("Ofast")
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 1e4 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, m, id[N], B[N];
inline int ask(vector < int > inp)
{
vector < int > vec;
for(auto x : inp) vec.push_back(id[x]);
int ret = (SZ(vec) < n? 0 : Query(vec));
return ret;
}
void _Answer(vector < int > vec)
{
vector < int > ret;
for(auto x : vec) ret.push_back(id[x]);
Answer(ret);
}
void solve(vector < int > inp)
{
int _m = SZ(inp) / n;
if(_m == 1)
{
_Answer(inp);
return;
}
int mid = _m >> 1;
vector < int > help, cop = inp;
for(int i = SZ(inp) - 1; ~i; i --)
{
cop.erase(cop.begin() + i);
if(ask(cop) >= mid)
{
help.push_back(inp[i]);
}
else
{
cop.insert(cop.begin() + i, inp[i]);
}
}
solve(cop);
solve(help);
}
void Solve(int _n, int _m)
{
n = _n;
m = _m;
vector < int > vec;
for(int i = 1; i <= n * m; i ++)
{
id[i] = i;
vec.push_back(i);
}
shuffle(id + 1, id + n * m + 1, rng);
solve(vec);
}
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
400 KB |
Output is correct |
2 |
Correct |
10 ms |
340 KB |
Output is correct |
3 |
Correct |
10 ms |
404 KB |
Output is correct |
4 |
Correct |
10 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
340 KB |
Output is correct |
6 |
Correct |
10 ms |
408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
227 ms |
788 KB |
Output is correct |
2 |
Correct |
243 ms |
556 KB |
Output is correct |
3 |
Correct |
229 ms |
540 KB |
Output is correct |
4 |
Correct |
225 ms |
588 KB |
Output is correct |
5 |
Correct |
243 ms |
668 KB |
Output is correct |
6 |
Correct |
230 ms |
668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
940 ms |
720 KB |
Output is correct |
2 |
Correct |
1106 ms |
800 KB |
Output is correct |
3 |
Correct |
1089 ms |
852 KB |
Output is correct |
4 |
Correct |
1034 ms |
748 KB |
Output is correct |
5 |
Correct |
1082 ms |
748 KB |
Output is correct |
6 |
Correct |
1103 ms |
940 KB |
Output is correct |