QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648110#9432. PermutationDjangle162857AC ✓277ms3936kbC++233.2kb2024-10-17 17:05:042024-10-17 17:05:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 17:05:04]
  • 评测
  • 测评结果:AC
  • 用时:277ms
  • 内存:3936kb
  • [2024-10-17 17:05:04]
  • 提交

answer

// #define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'

#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif

#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif

#ifdef LOCAL
#define debugv(x)                   \
	cerr << setw(4) << #x << ":: "; \
	for (auto i : x)                \
		cerr << i << " ";           \
	cerr << endl
#else
#define debugv(x)
#endif

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
	out << x.fir << " " << x.sec << endl;
	return out;
}
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
int n, cnt = 0;
int ans[N], a[N];
void init()
{
	cin >> n;
	cnt = 0;
#ifdef LOCAL
	vector<int> vis(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		ans[i] = i;
	}
	for (int i = 1; i <= n * 1000; i++) {
		int x = rng() % n + 1;
		int y = rng() % n + 1;
		swap(ans[x], ans[y]);
	}
	/*for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;*/
	// cout << endl;
	// FINISH
#endif
}
int query(vector<int>& v)
{
	cnt++;
	assert(cnt <= 6666);
	assert(v.size() == n + 1);
	int tot = 0;
#ifdef LOCAL
	/*cout << "0 ";
	for (int i = 1; i <= n; i++) {
		cout << v[i] << " ";
	}
	cout << endl;*/
	for (int i = 1; i <= n; i++) {
		if (ans[i] == v[i])
			tot++;
	}
	// cout << "! " << tot << endl;
#else
	cout << "0 ";
	for (int i = 1; i <= n; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cin >> tot;
#endif
	return tot;
}
void getans(int l, int r, vector<int> v)
{
	/*cout << " getans " << l << " " << r << endl;
	debugv(v);*/
	assert(v.size() == r - l + 1);
	if (l == r) {
		a[l] = v[0];
		return;
	}
	int mid = (l + r) >> 1;
	shuffle(v.begin(), v.end(), rng);
	vector<int> left, right;
	int st = 0, ed = 1;
	while (ed < v.size()) {
		ed = max(ed, st + 1);
		vector<int> q(n + 1, v[st]);
		for (int i = mid + 1; i <= r; i++) {
			q[i] = v[ed];
		}
		int res = query(q);
		if (res == 2) {
			for (int i = st; i < ed; i++) {
				left.push_back(v[i]);
			}
			right.push_back(v[ed]);
			st = ed + 1;
		}
		else if (res == 0) {
			for (int i = st; i < ed; i++) {
				right.push_back(v[i]);
			}
			left.push_back(v[ed]);
			st = ed + 1;
		}
		else {
			ed++;
		}
		if (left.size() == mid - l + 1) {
			for (int i = st; i < v.size(); i++) {
				right.push_back(v[i]);
			}
			break;
		}
		if (right.size() == r - mid) {
			for (int i = st; i < v.size(); i++) {
				left.push_back(v[i]);
			}
			break;
		}
	}
	getans(l, mid, left);
	getans(mid + 1, r, right);
}
void solve()
{
	init();
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		v.push_back(i);
	}
	getans(1, n, v);
	// cout << cnt << endl;
	cout << "1 ";
	for (int i = 1; i <= n; i++) {
#ifdef LOCAL
		assert(a[i] == ans[i]);
#endif
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3892kb

input:

5
0
1
2
0
2
2

output:

0 5 5 5 4 4 
0 3 3 3 2 2 
0 3 3 3 1 1 
0 2 2 3 2 2 
0 3 4 3 3 3 
0 1 1 1 1 5 
1 3 4 2 1 5 

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 249ms
memory: 3636kb

input:

1000
2
1
0
2
1
1
2
2
2
1
1
1
0
2
1
1
0
1
2
1
0
0
1
0
2
1
0
1
1
1
1
1
1
1
1
1
2
0
2
0
0
0
1
1
1
2
1
1
0
2
1
2
1
1
2
1
1
1
2
1
2
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
1
2
0
2
1
0
2
1
2
2
1
1
1
2
1
1
1
1
0
0
1
1
1
1
1
1
2
1
0
2
0
0
2
2
1
1
0
1
1
2
1
1
2
1
1
0
2
1
1
0
1
1
1
1
0
0
1
2
2
1
1
1
1
1
0
1
0
0
1
0...

output:

0 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 204 20...

result:

ok Accepted

Test #3:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

3
0
0

output:

0 2 2 3 
0 1 3 1 
1 3 1 2 

result:

ok Accepted

Test #6:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

4
1
2
2
0

output:

0 3 3 4 4 
0 3 3 1 1 
0 3 4 3 3 
0 1 1 1 2 
1 3 4 2 1 

result:

ok Accepted

Test #7:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

6
1
0
2
0
2
1
2
2

output:

0 5 5 5 6 6 6 
0 5 5 5 3 3 3 
0 2 2 2 1 1 1 
0 2 2 3 2 2 2 
0 3 4 3 3 3 3 
0 1 1 1 1 1 6 
0 1 1 1 1 1 5 
0 1 1 1 1 6 1 
1 3 4 2 1 6 5 

result:

ok Accepted

Test #8:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

7
1
0
2
2
0
0
0
0
2

output:

0 5 5 5 5 4 4 4 
0 5 5 5 5 1 1 1 
0 7 7 7 7 6 6 6 
0 7 7 2 2 7 7 7 
0 1 1 3 3 1 1 1 
0 7 3 7 7 7 7 7 
0 1 1 1 2 1 1 1 
0 4 4 4 4 4 4 5 
0 6 6 6 6 6 5 6 
1 3 7 2 1 6 5 4 

result:

ok Accepted

Test #9:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

8
1
2
0
1
0
1
2
2
2
2
0
0
0

output:

0 2 2 2 2 7 7 7 7 
0 2 2 2 2 8 8 8 8 
0 5 5 5 5 3 3 3 3 
0 4 4 4 4 6 6 6 6 
0 4 4 4 4 1 1 1 1 
0 3 3 7 7 3 3 3 3 
0 3 3 2 2 3 3 3 3 
0 3 7 3 3 3 3 3 3 
0 2 2 2 1 2 2 2 2 
0 5 5 5 5 5 5 8 8 
0 4 4 4 4 4 4 6 6 
0 5 5 5 5 5 6 5 5 
0 8 8 8 8 8 8 8 4 
1 3 7 2 1 6 5 4 8 

result:

ok Accepted

Test #10:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

9
1
1
2
2
2
2
2
1
2
0
0
2
2
2
0

output:

0 3 3 3 3 3 2 2 2 2 
0 3 3 3 3 3 9 9 9 9 
0 3 3 3 3 3 6 6 6 6 
0 1 1 1 1 1 5 5 5 5 
0 7 7 7 7 7 4 4 4 4 
0 7 7 7 9 9 7 7 7 7 
0 2 2 2 1 1 2 2 2 2 
0 3 3 7 3 3 3 3 3 3 
0 3 3 2 3 3 3 3 3 3 
0 7 3 7 7 7 7 7 7 7 
0 9 9 9 9 1 9 9 9 9 
0 4 4 4 4 4 4 4 6 6 
0 5 5 5 5 5 5 5 8 8 
0 5 5 5 5 5 5 4 5 5 
0 6 6 ...

result:

ok Accepted

Test #11:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

10
1
1
1
2
0
2
1
2
2
2
2
1
0
1
2
0
0

output:

0 1 1 1 1 1 9 9 9 9 9 
0 1 1 1 1 1 10 10 10 10 10 
0 1 1 1 1 1 7 7 7 7 7 
0 1 1 1 1 1 5 5 5 5 5 
0 6 6 6 6 6 3 3 3 3 3 
0 10 10 10 9 9 10 10 10 10 10 
0 3 3 3 7 7 3 3 3 3 3 
0 3 3 3 1 1 3 3 3 3 3 
0 3 3 10 3 3 3 3 3 3 3 
0 3 7 3 3 3 3 3 3 3 3 
0 1 1 1 1 9 1 1 1 1 1 
0 2 2 2 2 2 2 2 2 6 6 
0 2 2 2 2 ...

result:

ok Accepted

Test #12:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

11
2
0
0
0
0
2
1
2
0
2
2
0
0
1
2
2
2
2

output:

0 1 1 1 1 1 1 6 6 6 6 6 
0 8 8 8 8 8 8 10 10 10 10 10 
0 4 4 4 4 4 4 9 9 9 9 9 
0 2 2 2 2 2 2 3 3 3 3 3 
0 11 11 11 11 11 11 7 7 7 7 7 
0 7 7 7 5 5 5 7 7 7 7 7 
0 3 3 3 10 10 10 3 3 3 3 3 
0 3 3 3 9 9 9 3 3 3 3 3 
0 10 10 7 10 10 10 10 10 10 10 10 
0 3 7 3 3 3 3 3 3 3 3 3 
0 9 9 9 9 9 5 9 9 9 9 9 
0...

result:

ok Accepted

Test #13:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

12
1
1
1
0
2
1
1
2
2
1
2
0
2
2
0
1
2
1
0
2
2
0
0

output:

0 12 12 12 12 12 12 2 2 2 2 2 2 
0 12 12 12 12 12 12 8 8 8 8 8 8 
0 12 12 12 12 12 12 11 11 11 11 11 11 
0 12 12 12 12 12 12 10 10 10 10 10 10 
0 3 3 3 3 3 3 4 4 4 4 4 4 
0 5 5 5 5 5 5 7 7 7 7 7 7 
0 5 5 5 5 5 5 9 9 9 9 9 9 
0 5 5 5 5 5 5 6 6 6 6 6 6 
0 7 7 7 1 1 1 7 7 7 7 7 7 
0 10 10 10 3 3 3 10 1...

result:

ok Accepted

Test #14:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

13
2
2
2
2
2
1
2
2
1
2
0
1
0
2
2
2
2
0
1
2
2
0
1
2
2

output:

0 4 4 4 4 4 4 4 12 12 12 12 12 12 
0 7 7 7 7 7 7 7 6 6 6 6 6 6 
0 9 9 9 9 9 9 9 3 3 3 3 3 3 
0 13 13 13 13 13 13 13 11 11 11 11 11 11 
0 10 10 10 10 10 10 10 2 2 2 2 2 2 
0 1 1 1 1 1 1 1 5 5 5 5 5 5 
0 1 1 1 1 1 1 1 8 8 8 8 8 8 
0 1 1 1 1 4 4 4 1 1 1 1 1 1 
0 7 7 7 7 10 10 10 7 7 7 7 7 7 
0 7 7 7 7 ...

result:

ok Accepted

Test #15:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

14
1
0
0
0
1
0
0
0
2
0
0
2
0
2
1
2
2
1
0
1
1
2
1
2
0
0
0
0

output:

0 8 8 8 8 8 8 8 6 6 6 6 6 6 6 
0 8 8 8 8 8 8 8 9 9 9 9 9 9 9 
0 5 5 5 5 5 5 5 1 1 1 1 1 1 1 
0 12 12 12 12 12 12 12 4 4 4 4 4 4 4 
0 2 2 2 2 2 2 2 3 3 3 3 3 3 3 
0 2 2 2 2 2 2 2 7 7 7 7 7 7 7 
0 11 11 11 11 11 11 11 13 13 13 13 13 13 13 
0 14 14 14 14 1 1 1 14 14 14 14 14 14 14 
0 10 10 10 10 4 4 4 ...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

15
1
2
1
1
1
0
2
1
1
2
0
0
2
2
1
2
0
2
0
2
2
0
2
1
2
0
0
0
2
2
2
2

output:

0 11 11 11 11 11 11 11 11 13 13 13 13 13 13 13 
0 11 11 11 11 11 11 11 11 8 8 8 8 8 8 8 
0 12 12 12 12 12 12 12 12 5 5 5 5 5 5 5 
0 12 12 12 12 12 12 12 12 2 2 2 2 2 2 2 
0 12 12 12 12 12 12 12 12 3 3 3 3 3 3 3 
0 12 12 12 12 12 12 12 12 4 4 4 4 4 4 4 
0 15 15 15 15 15 15 15 15 6 6 6 6 6 6 6 
0 1 1 ...

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 235ms
memory: 3928kb

input:

975
0
2
2
1
1
1
2
1
1
2
0
2
0
1
1
1
1
2
1
0
1
1
1
0
0
2
1
0
1
1
2
1
0
2
1
0
2
1
1
1
1
0
0
0
0
1
2
1
1
0
0
1
1
1
0
2
1
2
2
0
0
1
1
1
2
2
0
1
1
1
2
1
0
1
1
0
0
2
1
0
1
2
2
1
0
1
1
0
1
2
0
2
1
1
1
2
1
2
0
1
1
2
1
0
1
1
1
1
0
2
1
1
1
1
0
2
0
2
2
0
1
0
1
0
2
1
1
1
1
2
0
0
0
2
1
2
0
0
2
1
1
1
0
2
1
1
2
0
...

output:

0 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 288 28...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 253ms
memory: 3696kb

input:

976
0
0
1
0
0
1
0
0
1
2
1
1
0
1
2
2
0
1
1
0
1
1
2
1
1
0
1
2
1
0
0
1
1
0
1
0
0
1
0
1
0
1
2
1
2
0
0
1
0
1
0
0
2
0
1
2
1
1
1
1
2
2
1
1
0
0
2
2
2
2
1
1
1
2
1
2
1
1
2
1
2
1
0
1
1
2
0
1
1
1
2
1
0
1
0
1
1
1
1
1
1
2
2
0
1
1
0
1
2
1
0
1
2
1
2
2
1
1
1
1
0
1
0
1
1
2
1
1
1
1
1
2
1
0
2
1
0
0
1
2
0
0
2
2
1
1
2
1
...

output:

0 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 249 24...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 226ms
memory: 3628kb

input:

977
0
2
2
2
1
2
1
2
0
0
0
0
0
1
1
1
2
1
1
1
0
1
2
0
1
2
0
0
2
1
0
1
2
1
2
1
2
1
2
2
0
1
0
1
2
0
1
1
2
1
1
1
2
0
1
0
1
2
1
1
2
1
0
2
1
1
1
0
0
1
2
0
1
1
2
2
1
0
1
0
1
1
1
1
1
0
2
0
1
0
0
1
2
1
2
2
1
2
1
1
1
2
1
1
2
2
1
1
2
0
0
1
1
1
0
1
1
1
1
1
2
0
2
2
0
2
1
1
1
1
1
1
2
1
2
0
1
1
1
1
0
2
0
1
0
1
0
0
...

output:

0 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 489 48...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 256ms
memory: 3764kb

input:

978
0
1
1
1
0
0
1
0
2
0
2
1
0
1
2
0
1
2
1
1
1
0
0
0
1
0
1
0
1
2
1
0
2
1
0
1
2
2
1
1
1
1
1
2
0
2
2
1
0
0
2
1
1
1
1
2
1
1
1
2
1
1
1
2
1
0
2
2
1
0
1
1
1
0
1
0
2
1
1
0
2
0
1
1
1
2
1
1
0
1
1
1
1
1
2
2
0
1
1
0
1
0
2
1
2
0
1
0
1
1
1
1
2
1
0
2
0
2
1
0
1
1
1
1
0
0
1
2
1
1
2
1
2
1
2
1
1
1
1
1
1
2
1
0
1
1
0
1
...

output:

0 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 40...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 252ms
memory: 3692kb

input:

979
0
0
1
0
1
1
0
1
1
0
0
0
1
0
2
2
0
1
1
1
2
2
1
1
2
1
0
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
0
1
1
0
1
2
1
0
1
1
1
2
1
2
2
1
2
1
2
1
2
1
2
0
2
1
1
1
0
0
1
2
0
2
0
1
0
1
0
1
1
2
1
0
0
0
0
1
2
1
0
0
1
1
1
1
1
1
0
1
1
2
1
1
2
1
1
2
0
2
1
0
1
0
1
2
1
2
2
2
0
1
0
1
0
1
0
0
2
0
1
1
2
2
1
0
1
0
0
2
2
1
1
0
0
0
...

output:

0 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 829 82...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 276ms
memory: 3688kb

input:

980
2
1
1
0
2
0
0
1
1
2
1
1
1
2
1
0
2
1
0
1
1
1
1
0
1
1
2
2
1
0
1
2
1
1
1
0
1
0
1
0
1
2
2
0
0
1
1
0
1
1
1
0
2
1
0
0
2
1
0
2
1
2
2
0
1
0
1
0
0
1
1
1
0
1
2
1
1
2
1
0
1
0
0
1
1
2
2
2
1
1
2
2
1
1
0
2
1
2
2
0
1
1
1
1
1
1
2
1
0
2
1
0
1
0
1
2
1
2
1
0
1
0
1
2
1
1
0
2
1
0
0
1
0
1
1
1
2
2
1
0
2
2
1
1
2
1
0
2
...

output:

0 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 353 35...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 256ms
memory: 3692kb

input:

981
2
2
0
2
1
2
2
2
1
1
1
0
1
1
1
0
1
0
2
2
1
0
2
1
1
1
1
1
0
0
1
0
1
2
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
1
2
1
0
1
2
0
1
1
2
0
1
1
1
0
1
1
2
1
1
0
0
1
0
0
2
0
0
1
0
2
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
2
1
2
0
1
1
1
1
1
0
1
1
2
2
2
1
2
1
0
2
2
1
2
1
2
0
1
2
0
1
1
2
1
1
1
0
2
1
1
0
0
1
2
...

output:

0 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 76...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 246ms
memory: 3696kb

input:

982
0
2
1
1
1
1
1
0
1
2
1
0
0
1
0
1
1
1
0
2
1
0
0
0
1
0
0
2
2
1
2
2
2
1
2
2
1
1
1
0
0
2
1
1
1
0
0
1
1
1
1
2
1
1
1
1
1
0
1
2
2
2
0
1
2
2
1
2
0
1
0
1
0
1
1
0
2
1
1
1
1
0
2
1
2
1
2
0
2
1
1
0
1
2
1
1
1
1
1
0
1
2
1
2
1
0
0
1
1
1
1
2
1
1
0
2
0
2
1
1
1
2
0
1
0
2
1
1
2
0
2
0
0
0
1
1
1
1
2
0
1
1
1
1
1
1
1
1
...

output:

0 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 258 25...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 266ms
memory: 3768kb

input:

983
0
1
1
1
2
0
1
1
1
2
2
1
1
0
1
2
2
2
2
2
1
2
1
2
1
0
0
2
1
0
0
1
1
2
0
1
1
1
0
0
1
0
0
0
1
0
1
1
1
1
1
1
0
2
0
1
0
1
1
2
2
1
2
1
0
1
1
2
1
0
2
1
1
2
2
1
0
2
1
1
1
2
1
1
0
2
1
1
1
0
1
1
1
1
2
1
1
1
1
0
1
2
1
0
1
2
1
1
2
2
1
2
0
1
2
2
1
2
0
1
2
1
0
1
1
2
1
1
2
1
2
2
1
2
2
0
2
1
1
1
1
2
0
1
1
1
2
1
...

output:

0 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 369 36...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 234ms
memory: 3684kb

input:

984
1
0
0
1
1
1
1
2
1
2
1
2
1
2
0
1
1
0
2
2
2
1
0
1
1
0
0
1
1
0
1
0
1
2
0
2
1
1
1
0
1
0
2
0
2
2
0
2
1
0
1
1
1
2
2
1
2
1
0
2
0
1
2
2
1
1
1
0
0
0
1
1
0
1
2
1
2
1
2
1
1
2
0
2
1
0
1
1
2
1
1
0
2
2
0
1
0
2
2
0
0
0
1
1
2
0
1
0
2
0
1
1
0
1
1
2
0
1
2
1
1
1
0
1
0
2
1
1
1
1
1
0
1
0
2
2
1
2
2
2
0
1
1
2
1
0
2
0
...

output:

0 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 320 32...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 262ms
memory: 3664kb

input:

985
2
1
1
1
1
0
1
2
0
1
1
1
1
0
2
1
0
1
2
1
2
1
2
2
0
2
0
2
0
0
1
2
1
1
1
1
0
1
1
1
1
2
1
1
1
1
1
1
1
2
2
1
0
1
1
1
0
0
1
0
2
2
1
1
1
2
1
1
2
2
1
1
1
1
0
1
0
1
2
2
1
1
0
1
0
1
1
1
1
1
2
0
1
1
1
1
0
1
1
1
0
1
1
1
2
2
2
0
0
1
1
1
0
1
1
2
2
1
1
1
2
0
2
0
1
1
0
2
2
0
0
1
1
2
0
0
0
1
1
1
2
2
2
2
1
1
0
1
...

output:

0 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 548 54...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 241ms
memory: 3696kb

input:

986
1
1
1
2
0
2
1
2
2
1
1
0
2
0
0
1
1
1
0
1
2
1
1
1
0
2
0
1
1
1
1
0
1
0
1
1
2
2
0
2
0
1
1
1
0
0
1
0
1
1
1
1
2
2
2
2
0
1
2
2
1
1
1
1
1
0
1
1
1
1
2
0
0
1
1
1
2
1
0
1
2
2
0
1
0
2
1
1
1
0
1
0
2
2
1
0
1
0
1
1
2
2
1
0
1
0
1
1
0
1
2
1
0
1
2
1
0
0
2
0
0
1
2
1
1
1
2
1
2
0
2
0
1
0
2
0
1
1
1
2
1
0
1
2
2
2
0
1
...

output:

0 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 972 97...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 239ms
memory: 3644kb

input:

987
1
0
1
0
0
1
0
0
1
1
1
2
0
0
0
1
1
2
0
0
0
2
1
1
2
0
1
2
2
1
0
1
0
1
0
2
2
2
1
0
1
2
1
0
0
2
2
1
1
1
1
1
0
1
1
1
0
2
1
1
1
2
0
2
1
1
0
1
1
0
1
0
2
2
0
0
1
1
1
1
0
0
0
1
1
0
0
0
2
1
0
2
0
0
1
1
1
1
0
1
1
1
1
1
2
2
1
1
1
0
1
1
1
0
1
1
1
1
2
2
2
0
1
2
0
0
1
1
2
2
0
1
1
0
1
0
2
0
2
1
2
1
0
0
0
1
2
1
...

output:

0 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 82...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 259ms
memory: 3700kb

input:

988
2
1
1
1
0
1
1
1
1
1
0
2
2
0
0
0
0
0
2
2
0
1
0
1
1
1
1
1
1
1
2
2
1
1
0
0
1
2
1
1
1
1
2
0
2
1
1
2
0
2
1
1
1
1
0
1
2
1
2
1
1
1
1
0
1
0
2
1
0
2
1
2
2
0
1
0
1
1
0
2
0
2
0
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
1
1
0
1
1
1
1
2
1
0
1
1
2
1
1
0
0
2
2
1
2
1
1
1
0
2
1
0
0
0
1
0
1
1
0
1
1
1
1
2
1
1
1
0
2
1
0
0
1
...

output:

0 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 278 27...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 266ms
memory: 3692kb

input:

989
1
1
0
1
2
1
1
1
2
1
2
1
1
1
2
0
2
0
2
2
1
1
1
1
0
1
1
2
0
1
1
1
1
0
2
0
2
1
0
2
0
2
2
1
1
0
0
0
2
2
0
2
1
1
1
1
1
1
2
1
2
2
0
2
2
0
0
2
1
2
1
1
0
0
2
0
2
1
2
2
1
2
1
0
1
1
1
2
2
2
1
1
1
1
0
2
1
2
1
1
2
2
1
1
1
1
1
1
1
0
2
2
1
0
1
0
2
1
1
2
1
1
1
2
1
2
1
1
1
1
1
1
0
1
2
2
0
1
2
0
0
0
0
1
2
2
1
1
...

output:

0 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 294 29...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 254ms
memory: 3648kb

input:

990
0
1
1
2
2
1
1
1
1
2
2
0
1
1
1
1
2
1
2
2
1
1
1
2
2
0
2
2
1
1
1
2
0
0
0
1
1
0
2
2
1
0
1
1
1
2
1
1
1
2
1
0
2
0
1
0
1
0
0
1
0
0
2
0
1
1
1
1
2
1
0
0
2
1
0
2
1
0
0
0
2
2
2
1
1
0
0
1
2
2
0
2
2
1
1
2
1
1
1
2
2
1
1
0
1
1
1
2
1
1
1
0
2
1
1
1
1
0
1
0
2
0
1
1
2
1
0
0
1
0
1
2
0
1
1
0
1
0
2
1
2
1
2
1
1
2
2
1
...

output:

0 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 402 40...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 274ms
memory: 3924kb

input:

991
1
2
2
0
0
0
0
0
1
0
2
1
0
1
1
0
1
1
0
0
2
2
0
2
1
0
1
2
1
0
1
1
2
1
0
0
2
1
1
1
1
0
1
1
2
0
2
2
1
1
1
1
1
1
1
2
1
0
1
1
1
2
1
2
2
0
2
1
1
2
0
1
1
2
1
1
0
1
2
1
0
1
1
0
1
1
1
2
2
2
1
1
2
1
1
0
0
1
1
0
0
2
0
2
2
1
1
1
0
1
2
0
2
1
0
1
0
0
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
0
0
0
1
1
1
...

output:

0 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 640 64...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 277ms
memory: 3640kb

input:

992
2
1
0
0
0
1
1
1
0
1
1
1
1
2
0
2
0
1
1
1
2
0
1
0
1
0
0
0
0
1
1
2
2
0
1
1
1
1
2
0
1
0
0
2
2
2
1
1
1
2
0
2
1
1
1
1
1
2
2
2
2
1
1
1
1
1
1
2
1
0
1
0
1
1
1
2
0
0
2
0
1
1
1
2
1
0
1
2
0
1
2
0
1
2
1
2
2
1
1
0
1
1
0
1
2
1
1
2
2
0
1
1
2
2
1
0
1
0
1
1
0
0
2
2
1
1
0
0
1
1
0
1
1
1
0
1
2
2
1
2
1
2
0
2
1
2
0
0
...

output:

0 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 566 56...

result:

ok Accepted

Test #35:

score: 0
Accepted
time: 277ms
memory: 3632kb

input:

993
2
1
1
2
0
0
2
1
1
2
1
1
1
1
1
1
1
0
1
1
1
0
1
2
0
1
2
0
2
0
0
1
1
2
0
2
1
2
0
1
2
1
1
1
2
1
2
1
1
1
1
0
1
1
2
0
0
0
0
1
2
1
0
2
0
2
0
1
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
2
2
1
2
1
2
0
1
0
0
0
1
1
1
1
1
1
1
0
1
0
1
1
1
2
0
1
2
0
0
1
1
1
0
1
1
1
1
1
1
2
2
2
1
2
2
1
0
0
0
0
2
1
0
1
1
2
1
0
1
0
...

output:

0 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 13...

result:

ok Accepted

Test #36:

score: 0
Accepted
time: 243ms
memory: 3936kb

input:

994
1
1
2
1
2
1
0
0
1
1
2
1
2
0
1
1
1
1
1
1
2
1
2
0
1
2
1
0
1
0
2
1
1
1
1
1
0
2
1
2
0
1
1
2
2
2
0
1
2
1
1
1
0
0
2
0
1
1
1
1
2
1
0
1
2
1
2
1
1
1
0
1
0
2
2
1
0
0
1
2
2
0
1
1
1
0
1
0
2
0
2
0
2
1
0
1
1
1
1
1
1
1
0
1
1
1
1
2
1
1
0
1
0
1
0
1
0
1
0
2
1
0
1
2
1
2
0
0
1
0
2
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
...

output:

0 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 90...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 238ms
memory: 3924kb

input:

995
1
0
1
0
1
0
2
0
0
0
2
1
1
1
1
0
2
2
1
2
0
1
1
1
1
1
0
1
1
2
0
2
0
0
0
1
0
0
0
2
0
0
1
2
2
0
0
2
2
2
1
1
1
1
2
2
1
2
1
1
2
1
1
0
1
1
1
1
1
0
2
1
0
1
0
0
1
0
2
0
0
2
1
0
0
1
1
1
0
1
1
0
2
2
1
1
0
1
0
1
1
1
0
0
1
2
1
2
2
0
1
1
1
1
2
0
1
2
1
0
0
1
1
1
2
2
2
2
2
0
1
1
0
1
1
1
1
1
2
1
2
2
1
2
1
2
1
0
...

output:

0 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 767 76...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 253ms
memory: 3696kb

input:

996
1
2
1
1
1
1
1
1
0
2
1
2
1
0
1
2
1
2
1
2
1
1
2
0
0
2
0
1
1
1
2
2
2
1
0
0
1
1
2
2
0
2
1
0
0
1
1
0
2
1
2
1
0
1
2
1
1
2
1
2
1
1
0
1
1
1
1
2
1
2
2
1
1
1
2
2
0
0
2
2
1
1
2
1
0
1
1
1
0
1
1
1
2
0
1
1
2
1
1
1
1
1
2
0
1
1
1
1
2
1
1
1
2
1
1
1
1
0
2
2
1
2
1
1
1
1
2
1
2
2
0
0
2
1
2
0
1
1
1
2
1
0
1
1
1
1
0
1
...

output:

0 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 838 83...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 239ms
memory: 3920kb

input:

997
0
0
0
0
1
1
1
1
2
0
0
2
1
1
1
1
0
1
0
0
1
2
1
1
1
0
0
1
1
0
1
2
1
0
1
0
0
1
0
1
0
0
0
1
2
0
1
1
0
1
1
2
1
1
1
0
0
1
1
0
0
0
1
2
1
1
0
0
1
1
1
1
2
0
2
1
1
1
0
2
1
0
0
2
1
1
1
2
2
0
1
0
0
2
2
0
1
1
2
1
1
2
1
2
1
1
1
1
2
2
1
2
0
1
1
0
1
1
1
2
2
0
1
1
2
1
2
0
1
0
1
0
1
1
2
0
2
1
0
2
1
2
0
2
0
2
2
1
...

output:

0 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 7...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 271ms
memory: 3696kb

input:

998
1
0
2
2
2
1
2
1
0
2
0
2
1
1
1
0
0
0
2
1
1
0
1
1
2
0
0
1
2
1
0
1
1
1
1
0
2
0
1
2
0
1
0
1
1
1
2
1
2
1
2
2
1
1
2
0
2
0
2
2
2
1
1
1
2
2
0
2
1
0
2
2
0
2
0
0
0
1
1
1
2
1
1
2
1
0
1
0
2
1
2
2
0
1
2
2
2
0
0
1
0
2
1
2
1
2
1
1
1
0
1
1
1
0
0
2
2
1
1
1
2
0
1
1
0
1
2
1
2
0
2
1
0
2
0
1
1
1
1
1
2
1
0
2
0
0
1
0
...

output:

0 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 863 86...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 263ms
memory: 3696kb

input:

999
1
0
2
1
0
0
2
0
1
1
1
0
1
0
0
2
2
2
2
0
1
1
1
1
1
1
2
0
1
2
1
2
2
1
1
2
1
0
1
2
0
1
1
2
1
1
2
1
1
1
1
2
2
0
1
1
2
1
1
1
0
1
0
2
0
1
0
2
1
2
0
1
0
1
1
0
1
2
1
1
2
1
1
1
1
2
1
0
2
0
0
2
0
1
0
1
1
2
0
0
0
1
1
1
1
1
2
1
0
1
1
1
2
2
1
0
1
2
2
0
1
0
1
1
1
1
2
1
1
1
1
1
1
1
0
1
0
2
1
0
1
1
0
2
1
2
1
1
...

output:

0 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 855 85...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed