QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34751#4251. Gamedutinmeow#60 2117ms42484kbC++2010.4kb2022-06-12 06:50:362024-05-26 00:55:32

Judging History

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

  • [2024-05-26 00:55:32]
  • 评测
  • 测评结果:60
  • 用时:2117ms
  • 内存:42484kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-12 06:50:36]
  • 提交

answer

// #include "game.h"

#define NDEBUG

#include <bits/stdc++.h>
using namespace std;

#pragma region debug

#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = next(v.begin()); i != v.end(); i++)
		os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = next(d.begin()); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
		}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = next(a.begin()); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = next(s.begin()); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = next(m.begin()); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
 cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif

#pragma endregion debug

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

namespace game {
	int N, K;
	vector<int> A, B;
	vector<vector<int>> G, H;

	void init_slow(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		iota(A.begin(), A.begin() + K, 0);
		B.assign(N, INT_MIN);
		iota(B.begin(), B.begin() + K, 0);
		G.resize(N);
		H.resize(N);
	}	

	bool add_teleporter_slow(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);
		
		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (dfsb(v, k))
					return true;
			return false;
		});

		return dfsa(s, A[t]) || dfsb(t, B[s]);
	}

	const int S = 700;

	vector<int> C, D;

	void init_fast(int _N, int _K) {
		N = _N;
		K = _K;
		A.assign(N, INT_MAX);
		B.assign(N, INT_MIN);
		C.assign(N, INT_MAX);
		D.assign(N, INT_MIN);
		for (int i = 0; i < K; i++) {
			A[i] = i;
			B[i] = i;
			C[i] = i / S; 
			D[i] = i / S;
		}
		G.resize(N);
		H.resize(N);
		dbg("_4\n", A, B, C, D);
	}

	bool add_teleporter_fast(int s, int t) {
		if (s < K && t < K)
			return t <= s;
		G[s].push_back(t);
		H[t].push_back(s);

		int p = -1;

		auto dfsc = y_combinator([&](auto dfsc, int u, int k) -> bool {
			if (C[u] <= k)
				return false;
			C[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : H[u])
				if (dfsc(v, k))
					return true;
			return false;
		});

		auto dfsd = y_combinator([&](auto dfsd, int u, int k) -> bool {
			if (k <= D[u])
				return false;
			D[u] = k;
			if (C[u] < D[u] || A[u] <= B[u])
				return true;
			else if (C[u] == D[u])
				p = u;
			for (int v : G[u])
				if (dfsd(v, k))
					return true;
			return false;
		});

		if (dfsc(s, C[t]) || dfsd(t, D[s]))
			return true;
		dbg("_4\n", s, t, A, B, C, D);
		if (p == -1)
			return false;
		int b = C[p];

		auto dfsa = y_combinator([&](auto dfsa, int u, int k) -> bool {
			if (A[u] <= k)
				return false;
			A[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : H[u])
				if (C[v] == D[v] && C[v] == b && dfsa(v, k))
					return true;
			return false;
		});

		auto dfsb = y_combinator([&](auto dfsb, int u, int k) -> bool {
			if (k <= B[u])
				return false;
			B[u] = k;
			if (A[u] <= B[u])
				return true;
			for (int v : G[u])
				if (C[v] == D[v] && C[v] == b && dfsb(v, k))
					return true;
			return false;
		});

		for (int i = b * S; i < min((b + 1) * S, K); i++) {
			for (int v : H[i])
				if (C[v] == D[v] && C[v] == b && dfsa(v, A[i]))
					return true;
			for (int v : G[i])
				if (C[v] == D[v] && C[v] == b && dfsb(v, B[i]));
					return true;
		}
		dbg(A, B, C, D);
		return false;
	}
}

bool fast = false;

void init(int N, int K) { 
	if (K >= 150000)
		fast = true;
	if (fast)
		game::init_fast(N, K); 
	else 
		game::init_slow(N, K);
}

int add_teleporter(int u, int v) { 
	if (fast)
		return game::add_teleporter_fast(u, v); 
	else 
		return game::add_teleporter_slow(u, v);
}

/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int K = read_int();
  std::vector<int> u(M), v(M);
  for (int i = 0; i < M; ++i) {
    u[i] = read_int();
    v[i] = read_int();
  }

  init(N, K);
  int i;
  for (i = 0; i < M; ++i) {
    int answer = add_teleporter(u[i], v[i]);
    if (answer != 0 && answer != 1) {
      i = -1;
      break;
    } else if (answer == 1) {
      break;
    }
  }
  printf("%d\n", i);
  return 0;
}
*/

#undef NDEBUG

详细

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 3800kb

input:

1 1
1
893123 893123
-1

output:

0

result:

ok interaction finished.

Test #2:

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

input:

9 9
29
893122 893124
893121 893127
893120 893124
893123 893121
893122 893131
893125 893131
893121 893126
893123 893126
893126 893131
893123 893131
893123 893125
893123 893124
893127 893125
893120 893126
893123 893120
893121 893131
893123 893127
893122 893126
893122 893127
893127 893131
893122 893125...

output:

28

result:

ok interaction finished.

Test #3:

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

input:

100 100
80
893180 893071
893134 893063
893150 893091
893127 893178
893142 893177
893153 893156
893127 893137
893174 893065
893127 893070
893126 893061
893171 893089
893173 893072
893153 893058
893156 893074
893151 893068
893136 893060
893120 893083
893073 893091
893148 893163
893073 893088
893156 89...

output:

80
80
80
59

result:

ok interaction finished.

Test #4:

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

input:

45 45
80
893143 893167
893122 893132
893123 893140
893120 893139
893158 893167
893154 893163
893133 893137
893133 893142
893135 893137
893121 893135
893137 893149
893141 893152
893122 893167
893128 893145
893140 893167
893122 893127
893134 893142
893122 893129
893141 893156
893146 893149
893123 8931...

output:

80
49

result:

ok interaction finished.

Test #5:

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

input:

100 100
80
893169 893058
893132 893065
893143 893068
893153 893167
893152 893182
893138 893162
893129 893163
893146 893164
893134 893180
893142 893167
893144 893059
893132 893064
893135 893091
893164 893068
893123 893179
893126 893060
893136 893140
893179 893081
893139 893181
893120 893057
893172 89...

output:

80
80
80
42

result:

ok interaction finished.

Test #6:

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

input:

100 100
80
893135 893081
893170 893076
893148 893075
893134 893159
893159 893073
893170 893088
893131 893138
893121 893166
893171 893168
893127 893137
893147 893145
893062 893076
893160 893059
893063 893088
893137 893073
893123 893182
893152 893170
893141 893172
893137 893087
893167 893085
893147 89...

output:

80
80
80
37

result:

ok interaction finished.

Test #7:

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

input:

100 100
80
893062 893075
893139 893156
893137 893083
893071 893075
893072 893080
893141 893060
893126 893179
893064 893081
893167 893077
893139 893165
893056 893085
893169 893182
893062 893087
893141 893078
893062 893078
893129 893176
893065 893077
893141 893181
893152 893158
893151 893078
893157 89...

output:

80
80
80
59

result:

ok interaction finished.

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #8:

score: 10
Accepted
time: 1ms
memory: 3880kb

input:

100 10
80
893135 893150
893174 893168
893159 893149
893162 893082
893158 893129
893072 893150
893088 893079
893155 893154
893086 893126
893078 893153
893177 893138
893057 893066
893151 893089
893076 893162
893165 893164
893085 893170
893084 893128
893074 893083
893138 893148
893147 893167
893071 893...

output:

80
31

result:

ok interaction finished.

Test #9:

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

input:

100 10
80
893087 893068
893090 893073
893077 893169
893159 893156
893170 893062
893081 893145
893076 893083
893128 893078
893132 893139
893181 893165
893155 893167
893167 893089
893065 893081
893068 893180
893150 893175
893066 893183
893060 893133
893086 893060
893072 893142
893084 893132
893151 893...

output:

80
10

result:

ok interaction finished.

Test #10:

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

input:

100 10
80
893136 893078
893085 893075
893173 893143
893132 893066
893066 893074
893149 893080
893152 893148
893179 893146
893174 893137
893082 893077
893140 893082
893080 893134
893171 893149
893070 893161
893087 893132
893168 893059
893086 893085
893159 893153
893143 893173
893167 893140
893062 893...

output:

80
25

result:

ok interaction finished.

Test #11:

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

input:

100 50
80
893180 893088
893174 893057
893168 893177
893080 893064
893061 893060
893086 893065
893169 893168
893182 893069
893079 893068
893177 893089
893064 893176
893175 893084
893068 893072
893076 893063
893071 893087
893074 893078
893070 893082
893090 893179
893179 893182
893063 893071
893173 893...

output:

80
19

result:

ok interaction finished.

Test #12:

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

input:

100 25
80
893065 893138
893153 893124
893163 893132
893121 893173
893170 893183
893128 893162
893063 893084
893174 893128
893163 893124
893148 893127
893127 893167
893146 893153
893157 893152
893077 893154
893067 893135
893174 893146
893156 893058
893120 893066
893151 893128
893087 893139
893144 893...

output:

80
80
80
14

result:

ok interaction finished.

Test #13:

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

input:

100 10
80
893171 893168
893173 893067
893132 893173
893060 893178
893062 893064
893077 893171
893135 893081
893089 893134
893091 893064
893086 893156
893173 893181
893133 893071
893070 893076
893154 893069
893172 893182
893138 893091
893151 893149
893162 893085
893132 893136
893125 893083
893173 893...

output:

80
80
80
13

result:

ok interaction finished.

Test #14:

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

input:

100 50
80
893171 893179
893169 893074
893139 893091
893159 893168
893078 893171
893162 893064
893080 893174
893125 893067
893156 893087
893152 893061
893063 893183
893069 893170
893086 893170
893154 893181
893069 893090
893131 893069
893075 893164
893088 893171
893131 893066
893154 893083
893153 893...

output:

80
80
80
9

result:

ok interaction finished.

Test #15:

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

input:

100 48
80
893089 893176
893085 893129
893129 893176
893083 893129
893141 893061
893083 893064
893166 893176
893064 893073
893141 893176
893085 893141
893085 893083
893061 893089
893073 893061
893129 893089
893129 893061
893141 893089
893073 893166
893083 893141
893166 893061
893083 893166
893129 893...

output:

80
68

result:

ok interaction finished.

Test #16:

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

input:

100 48
80
893168 893085
893072 893083
893072 893148
893145 893168
893083 893087
893145 893080
893085 893080
893182 893165
893182 893072
893182 893145
893087 893168
893145 893083
893148 893168
893165 893168
893072 893145
893072 893165
893182 893148
893165 893085
893148 893085
893145 893085
893165 893...

output:

80
80
13

result:

ok interaction finished.

Subtask #3:

score: 18
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 18
Accepted
time: 1ms
memory: 3844kb

input:

1000 10
80
893932 893218
893380 893370
893280 893263
893162 893561
893846 893370
893391 893342
893351 893619
893565 893342
893487 893723
893463 893114
893799 893840
893116 893441
893210 893715
893586 893630
893612 893924
893414 893035
893390 893253
893141 893115
893485 893520
893924 893878
893292 89...

output:

80
80
80
80
80
80
80
80
80
80
80
80
1

result:

ok interaction finished.

Test #18:

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

input:

1000 100
80
893512 892972
893438 893564
893648 893457
893558 893935
893376 893054
893861 893423
893145 893474
893644 893946
893336 893172
893850 893616
893261 893785
893760 893528
893373 893292
893465 893705
893048 893365
893330 893083
893594 893296
893279 893125
893188 893313
893536 893453
893668 8...

output:

80
56

result:

ok interaction finished.

Test #19:

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

input:

1000 100
80
893640 893021
893621 893584
892987 893336
893472 892977
893543 893228
893314 893623
893549 893545
893618 892972
893241 893381
893339 893277
893423 893676
893787 893947
893412 893867
893526 893881
892954 893865
893779 893945
893204 893474
893229 893295
893397 893600
893284 893829
893890 8...

output:

80
80
80
80
80
80
80
80
80
80
80
20

result:

ok interaction finished.

Test #20:

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

input:

1000 10
80
893630 893661
893243 893498
893009 893765
893016 893444
893442 893486
893037 893282
893800 893364
893482 893573
893083 893631
893680 893845
892952 893465
893061 893075
893838 893376
893452 893546
892990 893508
893114 892973
892991 893401
893404 893301
893086 893936
893257 892992
893820 89...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
15

result:

ok interaction finished.

Test #21:

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

input:

1000 500
80
893666 893929
893585 893608
893889 893683
893864 893568
893874 893523
893903 893487
893618 893794
893829 893804
893594 893482
893673 893497
893523 893878
893447 893527
893590 893853
893777 893514
893550 893237
893897 893540
893775 893778
893799 893622
893627 893621
893598 893530
893558 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
39

result:

ok interaction finished.

Test #22:

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

input:

1000 250
80
893027 893523
893258 893080
893847 893524
893720 893942
893660 893559
893031 893609
893219 892986
893616 893689
893286 893014
893184 893029
893833 893857
892978 893795
893434 893676
893789 892942
892952 893880
893705 893611
893075 893267
892948 893313
893150 893708
893030 893778
892929 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
60

result:

ok interaction finished.

Test #23:

score: 0
Accepted
time: 2ms
memory: 4012kb

input:

1000 100
80
893395 892948
893103 893673
893689 893615
892957 893475
893685 893445
892965 892951
892954 893469
893566 893605
893591 893865
893712 893584
893072 893453
893681 893490
893594 893206
893724 893481
892962 893647
893581 893832
893825 893010
893326 892940
893205 893665
893230 893462
893949 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
3

result:

ok interaction finished.

Test #24:

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

input:

1000 500
80
893592 893233
893222 893809
893786 893543
893661 893233
893362 893896
893432 893822
893603 893232
893830 893816
893894 893233
893782 893232
893935 893232
893445 893232
893875 893234
893331 893790
893716 893574
892964 893646
893677 893234
893460 893593
893037 893494
893500 893233
893012 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
32

result:

ok interaction finished.

Test #25:

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

input:

1000 480
80
893401 893764
893787 893211
893240 893127
893880 892971
893522 892984
893522 893015
893449 893401
893149 893224
893331 893784
893534 893063
893880 893120
893050 893928
893652 893023
893354 893594
893120 893870
893127 893790
893570 893182
892984 893629
893652 893182
893345 893447
893354 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
69

result:

ok interaction finished.

Test #26:

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

input:

1000 480
80
893907 893272
893478 893293
893886 892998
893490 893573
893038 893623
893781 892951
892940 893891
893834 893070
892964 893629
892940 893867
893437 893685
892950 893925
893572 892990
892950 893490
893454 893538
893907 893293
893489 893293
893591 893712
893908 893679
893336 893588
893781 8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
8

result:

ok interaction finished.

Subtask #4:

score: 30
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 30
Accepted
time: 11ms
memory: 6176kb

input:

30000 100
80
899506 888816
888591 894413
902184 906369
904197 896104
889550 895990
916079 915763
885883 899331
887259 885983
898484 887782
891896 904753
910535 893719
910133 891961
899807 898437
916401 895311
891348 887333
887544 916670
899351 905356
893259 915304
893328 903480
894439 897409
911242 ...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #28:

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

input:

30000 1000
80
888463 913925
892100 897945
913578 901104
890521 899049
895263 894452
913292 909544
905183 917349
885960 885393
889726 899618
910824 913325
901155 896320
885429 898265
900308 910523
904946 887937
886762 892781
888918 916215
886099 889793
885317 917406
892733 917151
893037 898842
896378...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
26

result:

ok interaction finished.

Test #29:

score: 0
Accepted
time: 10ms
memory: 6988kb

input:

30000 100
80
894521 909917
901995 912849
884977 917008
903366 905126
898211 902083
902834 896589
892563 903508
912525 897850
911679 901575
905919 897511
911480 909868
903623 897534
917191 888463
891138 891245
899943 897287
910082 891188
909593 890450
889548 885321
910460 905329
893972 889385
886431 ...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #30:

score: 0
Accepted
time: 6ms
memory: 6984kb

input:

30000 10
80
903385 897892
901499 897416
901684 888817
896553 889043
911436 891926
900347 888717
900444 913858
892209 906168
913793 911944
896231 905276
897882 911886
914209 916881
896877 889975
901214 912595
897884 896669
903532 885001
911544 916543
914413 888441
893885 915363
894985 913964
892328 9...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #31:

score: 0
Accepted
time: 1304ms
memory: 7492kb

input:

30000 1000
80
890517 916773
914690 905354
886694 897246
898826 904179
911030 917195
887996 898617
898053 909920
917009 895972
903355 910504
915250 886913
895885 910418
902854 904356
910687 909634
887159 904371
915737 891190
895082 888447
916943 906351
916836 885068
888219 915392
910073 888168
900294...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #32:

score: 0
Accepted
time: 411ms
memory: 7232kb

input:

30000 1000
80
897191 890469
906065 892509
885193 894316
885157 889260
912943 904052
916930 909659
914728 884742
896488 895555
902178 906152
911233 893445
914592 903728
892220 893410
902970 916889
893575 913577
888565 913378
909744 886927
890859 906250
890485 892591
903043 888565
898326 910029
889181...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #33:

score: 0
Accepted
time: 20ms
memory: 6888kb

input:

30000 100
80
896775 889886
912691 885186
903344 904285
911987 902661
901245 901417
903363 897519
890244 909528
890678 887966
903455 912343
889767 896674
899054 900598
894822 890273
896807 889040
897441 915376
893973 899773
901534 917461
905138 913392
893272 914202
910220 886381
902339 890184
889827 ...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #34:

score: 0
Accepted
time: 19ms
memory: 6704kb

input:

30000 1000
80
914155 886874
914451 891982
889630 912849
911697 886639
886283 888499
915316 903153
905795 889145
900801 898520
909350 890214
903743 890002
891614 903630
898022 887200
912325 901151
888879 914922
916341 888959
906427 914013
914045 897594
910181 900136
911119 905736
892916 916548
910659...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #35:

score: 0
Accepted
time: 7ms
memory: 6652kb

input:

30000 1000
80
891238 886498
890152 898163
893918 913474
892988 910835
895233 884761
886673 893765
892721 902707
893536 891731
893058 894484
893000 885364
884737 893711
916897 910246
916358 903621
892975 910812
887316 906001
892987 911506
890999 905106
893114 911954
901883 896354
893713 896402
911918...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #36:

score: 0
Accepted
time: 13ms
memory: 6704kb

input:

30000 1000
80
889476 916627
913621 899846
888754 893766
893685 897892
890845 916623
910047 913734
885368 913894
885359 916761
904432 890059
896646 911626
901025 902434
896084 904449
893250 898972
894891 891216
917068 893724
902764 916561
910446 903666
892990 910062
903145 900798
910482 886267
912489...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #37:

score: 0
Accepted
time: 1050ms
memory: 7776kb

input:

30000 1000
80
893245 900430
893814 905522
885753 892111
901900 911227
892997 887778
893021 904936
893442 917128
903300 893590
892980 912800
897330 893604
889436 893176
897681 893055
884744 893478
893556 914148
893704 886092
893070 911082
893412 906406
893633 910776
906428 893779
887921 893283
893483...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #38:

score: 0
Accepted
time: 152ms
memory: 6672kb

input:

30000 1000
80
893885 890594
893874 894363
886754 902186
915158 905586
901981 893223
893009 909684
893554 890744
888774 893474
893243 912929
910450 891859
898044 890320
892939 890971
896853 891674
896575 893817
893119 886620
892522 893935
898459 913661
893691 916329
915118 905566
912326 910157
906276...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #39:

score: 0
Accepted
time: 76ms
memory: 6652kb

input:

30000 1000
80
910146 903050
893925 905367
914653 889407
893633 889461
890748 893661
895483 899702
893339 905522
890550 903645
890290 902024
917487 887107
892566 892783
893567 898286
916656 900553
887084 893265
891232 888148
903917 909608
896690 892663
893213 902035
891347 893363
910610 893683
893633...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #40:

score: 0
Accepted
time: 34ms
memory: 7160kb

input:

30000 1000
80
891230 899516
906396 896856
911875 886575
891515 906336
900765 914221
913429 903421
900858 885623
909699 889900
900514 913311
888774 886053
894352 898655
894296 915038
896484 901738
889226 904006
900432 901200
889076 913326
895878 900382
905190 904476
914627 898496
896336 885774
911872...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #41:

score: 0
Accepted
time: 862ms
memory: 7752kb

input:

30000 1000
80
894611 904362
912986 899100
889698 896743
902613 893973
910060 912084
898229 897665
903829 895157
916792 897316
912628 892282
906447 900581
894848 906201
914270 892649
914103 894141
899345 886011
901518 909743
886280 903763
896782 905963
905284 899388
896930 900037
884764 885136
903225...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #42:

score: 40
Accepted
time: 81ms
memory: 31132kb

input:

300000 100
80
935208 598686
1006216 944423
899936 789642
631510 1019517
861576 814849
819952 979323
866363 935431
1004490 857766
800039 958542
631012 931811
786960 1034912
804779 909212
903567 925801
1036293 1023188
1005826 649117
1015361 959205
642550 1041096
1031082 950568
974480 1041339
965839 95...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #43:

score: 0
Accepted
time: 4ms
memory: 20200kb

input:

300000 1000
80
842033 625275
948869 858082
804294 862794
807273 972417
641903 990888
1003415 835644
846593 645993
915227 803725
873198 896544
1034258 1023875
859013 970477
810330 842682
653168 634310
971842 874872
908591 808519
1021573 939101
955268 996112
860773 889831
867884 815782
983467 979924
8...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
32

result:

ok interaction finished.

Test #44:

score: 0
Accepted
time: 4ms
memory: 20064kb

input:

300000 2000
80
1008246 647544
852347 992363
893364 929732
932481 997689
937371 937210
952598 786784
943199 934150
968272 1003457
647425 967739
841624 826411
941155 831606
1006890 869679
641582 911569
959518 865127
861337 601594
1022641 858487
907070 787260
952869 653460
650271 802738
877662 630648
9...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
42

result:

ok interaction finished.

Test #45:

score: 0
Accepted
time: 116ms
memory: 41956kb

input:

300000 100
80
920740 1033629
1000297 900307
840449 644532
623023 871478
807240 960681
910888 988471
921188 818584
847136 918717
788111 883194
861093 1011656
1029149 651571
848247 626090
1018804 888494
1037327 986756
1018437 851461
830142 828666
868785 866477
1032763 933148
980230 917391
799190 10485...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #46:

score: 0
Accepted
time: 105ms
memory: 38528kb

input:

300000 100
80
822060 600488
981396 809989
858579 966006
954676 900969
795745 653981
988292 653727
1043184 1004386
976171 1036875
805492 1044930
937640 919636
964656 930695
971395 914202
1042672 1012299
814589 902330
868678 990808
896658 1043466
942732 997637
982473 799960
812064 846834
814117 912789...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

ok interaction finished.

Test #47:

score: -40
Wrong Answer
time: 2117ms
memory: 42484kb

input:

300000 150000
80
970943 990127
970823 926753
622911 632192
649185 1014219
645779 1048032
1000794 1005989
923448 970103
997874 1039757
1009755 1034972
962671 941447
599797 952833
929476 941115
626679 999763
938497 1045020
962748 980020
630151 1003034
653442 1008712
928577 990469
647227 918289
1012416...

output:

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
...

result:

wrong answer Wrong Answer [1]