Submission #52600656

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
template<integral T,T Q=2>constexpr T inf=numeric_limits<T>::max()/Q-1;
template<class T,class S=T>inline bool umin(T&m,S&&x){return x<m?m=x,1:0;}
template<class T,class S=T>inline bool umax(T&m,S&&x){return m<x?m=x,1:0;}
auto&operator<<(ostream&o,ranges::range auto&&r)requires(!requires{string{r};}){int f=0,u=&o!=&cerr;o<<"["+u;for(auto&&x:r)(f++?o<<", "+u:o)<<x;return o<<"]"+u;}
auto&operator<<(ostream&o,auto&&t)requires requires{tuple_cat(t);}{int f=0,u=&o!=&cerr;o<<"<"+u;apply([&](auto&...x){(((f++?o<<", "+u:o)<<x),...);},t);return o<<">"+u;}
#ifdef BIZON
    #define rr(v...) [](auto&&...x){ cerr << boolalpha << #v << " "; int _=0; ((cerr<<",="[!_++]<<' '<<x),...)<<endl; }(v);
#else
    #define rr(...) ;
    #define endl '\n'
#endif
#define bb(c) begin(c), end(c)
#define ff(T, name, args...) function<T(args)> name = [&](args)->T
#define ee(e) [&](auto&&it) { return e; }
#define jj(v...) v; [](auto&...x){(cin>>...>>x);}(v);
#define ii(v...) int jj(v)
using ll = decltype(1LL);


void run_case(const size_t ____case) { // rr(____case)
    ii(n, qn)
    
    vector<unordered_set<int>> g(n);
    
    set<int> bigs;
    unordered_map<ll, int> ps;
    
    const int D = sqrt(n) * 0.75;
    
    int ans = 0, M = 998244353;
    while(qn--) {
        ll jj(a, b, c)
        int t = 1 + (((a * (1 + ans)) %M) %2);
        int u = 1 + (((b * (1 + ans)) %M) %n);
        int v = 1 + (((c * (1 + ans)) %M) %n);
        
        --u; --v;
        if(t == 1) {
            g[u].insert(v);
            g[v].insert(u);
            
            auto add = [&](int i, int j) {
                g[i].insert(j);
                if(size(g[i]) >= D) bigs.insert(i);
                else {
                    for(int p : g[i]) if(p != j) {
                        auto [x, y] = minmax(p, j);
                        ps[ll(x) * n + y] = i;
                    }
                }
            };
            
            add(u, v);
            add(v, u);
        } else {
            int res = 0;
            
            for(int x : bigs) {
                if(auto &s = g[x]; s.count(v) && s.count(u)) {
                    res = x + 1;
                    break;
                }
            }
            
            auto [x, y] = minmax(u, v);
            if(auto it = ps.find(ll(x)*n+y); it != end(ps)) {
                res = it->second + 1;
            }
            
            cout << res << endl;
            ans = res;
        }
    }
}

int main() {
    if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
    cin.tie(0)->sync_with_stdio(0);
    
    size_t tn = 1; //cin>>tn;
    for(size_t t=1; t<=tn; ++t) run_case(t);
    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In lambda function:
Main.cpp:46:31: warning: comparison of integer expressions of different signedness: ‘std::unordered_set<int>::size_type’ {aka ‘long unsigned int’} and ‘const int’ [-Wsign-compare]
   46 |                 if(size(g[i]) >= D) bigs.insert(i);
      |                    ~~~~~~~~~~~^~~~
Main.cpp: In function ‘void run_case(size_t)’:
Main.cpp:22:28: warning: unused parameter ‘____case’ [-Wunused-parameter]
   22 | void run_case(const size_t ____case) { // rr(____case)
      |               ~~~~~~~~~~~~~^~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:79:62: warning: suggest braces around empty body in an ‘if’ statement [-Wempty-body]
   79 |     if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
      |                                                              ^

Judge Result