Submission #1164903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164903		ahmedosamaezz	Pictionary (COCI18_pictionary)	C++20	140 / 140	149 ms	6556 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
#define imfaast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
  struct node{
    int L, R;
    int l , r;
  };

  const int N=2e5 + 5;
  int parent[N];
  int find(int i){
    if(parent[i] == -1)return i;
    return parent[i] = find(parent[i]);
  }
  void merge(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    parent[y] = x;
  }
void solve(){
  int n, m, q;
  cin>>n>>m>>q;
  
 //for(auto it : v)cout << it.second <<' ';return;
  vector<node>a;
  for(int i = 0; i < q; i++){
    int z, b;
    cin>>z>>b;
    node x;
    x.L = z, x.R = b;
    x.l = 0, x.r = m;
    a.push_back(x);
  }
  bool lessa = 1;
  while(lessa){
    lessa = 0;
    vi v[m + 1];
    for(int i = 0; i < q; i++){
      if(a[i].l + 1 != a[i].r){
        lessa = 1;
        v[a[i].l + a[i].r >> 1].push_back(i);
      }
    }
    memset(parent, -1, sizeof parent);
    for(int i = 1; i <= m; i++){
      // i-th day
      for(int j = (m - i + 1) * 2; j <= n; j += (m - i + 1))merge(m - i + 1, j);
      for(auto j : v[i]){
        if(find(a[j].R) == find(a[j].L)){
            a[j].r = i;
        }else {
          a[j].l = i;
        }
      }
    }
  }
  for(int i = 0; i < q; i++)cout<<a[i].r<<'\n';
}

int main(){
    imfaast
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }  

}

• 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