//{ <defines>
#include <bits/stdc++.h>
using namespace std;
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")
#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)
#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _ << ' ' <<
#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back
#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;
inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//int md = 998244353;
//inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
//inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
//inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
//inline int m_prod(int a, int b) {re 1ll * a * b % md;}
//
//int m_bpow(ll A, ll b) {
// int a = A % md;
// ll ans = 1;
// for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
// (ans *= ans) %= md;
// if(p & b)
// (ans *= a) %= md;
// }
// re ans;
//}
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e5 + 5;
int n, m, q;
int l[N], r[N], md[N], p[N], a[N], b[N];
list<int> t[N];
bool finish;
int get(int i) {re p[i] == i ? i : p[i] = get(p[i]);}
void unite(int i, int j) {p[get(i)] = get(j);}
void iteration() {
fo(n) p[i + 1] = i + 1;
for(int i = 0, j = m; i < m; ++i, --j) {
for(int v = j + j; v <= n; v += j)
unite(v, v - j);
for(int f : t[i]) {
if(get(a[f]) == get(b[f]))
r[f] = md[f];
else
l[f] = md[f] + 1;
md[f] = l[f] + r[f] >> 1;
}
t[i].clear();
}
finish = true;
fo(q) if(l[i] < r[i])
t[md[i]].pb(i), finish = false;
}
void solve() {
cin >> n >> m >> q;
finish = true;
fo(q) {
cin >> a[i] >> b[i];
l[i] = 0, r[i] = m - 1;
md[i] = (l[i] + r[i]) >> 1;
if(m > 1) t[md[i]].pb(i), finish = false;
}
while(!finish) iteration();
fo(q) cout << l[i] + 1 << '\n';
}
int main() {
#ifdef _LOCAL
freopen("in.txt", "r", stdin);
int tests; cin >> tests;
for(int test = 1; test <= tests; ++test) {
cerr << "case #" << test << endl;
solve();
cerr << endl;
}
#else
// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
#endif
return 0;
}
Compilation message
pictionary.cpp: In function 'void iteration()':
pictionary.cpp:83:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
md[f] = l[f] + r[f] >> 1;
~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
3712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
6496 KB |
Output is correct |
| 2 |
Correct |
47 ms |
6648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
8180 KB |
Output is correct |
| 2 |
Correct |
72 ms |
7800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
5496 KB |
Output is correct |
| 2 |
Correct |
97 ms |
5368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
105 ms |
5752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
6648 KB |
Output is correct |
| 2 |
Correct |
160 ms |
5656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
7672 KB |
Output is correct |
| 2 |
Correct |
275 ms |
7684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
345 ms |
8264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
454 ms |
8824 KB |
Output is correct |
| 2 |
Correct |
378 ms |
8696 KB |
Output is correct |
