제출 #1323967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323967		itsKiaRash	Pictionary (COCI18_pictionary)	C++20	140 / 140	147 ms	13616 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds; // find_by_order   order_of_key
// template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize ("Ofast")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#define int ll
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define testc int ttt;cin>>ttt;while(ttt--)
#define alll(x)	(x).begin(),(x).end()
#define pqi priority_queue<pii, vector<pii>, greater<pii>>
#define kill(x)  cout << x << '\n', exit(0)
#define rep(x) cout<<"report: "<<x<<endl;
#define endl '\n'
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define ff first
#define ss second
#define bg begin
#define rbg rbegin
#define sz size()
#define mset(x,y) memset(x,y,sizeof(x))
#define clr clear()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define vci vector<int>
#define sti set<int>
#define nl cout<<endl
#define upb upper_bound
#define lrb lower_bound
//ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
const ll inf = (ll)1e18 + 18;
const int maxn = 1e5 + 7, mod = 1e9 + 7; //998244353 1594778359 1540481779
int n, m, q;
vci save[maxn];
bool done;
pii Q[maxn], lr[maxn];
int sar[maxn], siz[maxn];
int get(int x){return(x == sar[x] ? x : sar[x] = get(sar[x]));}
void merge(int u, int v){
    int x = get(u), y = get(v);
    if(x == y) return;
    siz[x] += siz[y]; sar[y] = x;
}
void reset(){
    for(int i = 0 ; i <= n + 3 ; i ++) sar[i] = i, siz[i] = 1;
    for(int i = 0 ; i <= m + 3 ; i ++) save[i].clr; done = true;
    for(int i = 1 ; i <= q ; i ++){
        auto[l, r] = lr[i];
        if(r - l > 1){
            int mid = l + r >> 1;
            save[mid].pb(i);
            done = false;
        }
    }
}

int32_t main(){
    FAST_IO
    cin >> n >> m >> q ;
    for(int i = 1 ; i <= q ; i ++){
        cin >> Q[i].ff >> Q[i].ss ; lr[i] = {0, m + 1};
    }
    while(true){
        reset(); if(done) break;
        for(int mid = 1 ; mid <= m ; mid ++){
            int x = m - mid + 1;
            for(int i = x ; i + x <= n ; i += x){
                merge(i, i + x);
            }
            for(int i : save[mid]){
                auto[a, b] = Q[i];
                if(get(a) == get(b)) lr[i].ss = mid;
                else lr[i].ff = mid;
            }
        }
    }
    for(int i = 1 ; i <= q ; i ++) cout << lr[i].ss << endl;

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14