제출 #1271891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271891		ZeroCool	ICC (CEOI16_icc)	C++20	90 / 100	79 ms	632 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;;
#define ll long long
#define ar array
#define ld double
// #define int long long
#define all(v) v.begin(), v.end()

//  #pragma GCC optimize("O3,Ofast,unroll-loops ")

const int N = 3010;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct DSU{
    vector<int> p;

    DSU(int n){
        p.resize(n);
        iota(all(p), 0);
    }
    
    int fnd(int x){
        if(p[x] == x)return x;
        return p[x] = fnd(p[x]);
    }

    bool upd(int a,int b){
        a = fnd(a);
        b = fnd(b);
        if(a == b)return 0;
        p[a] = b;
        return 1;
    }
};

bool ask(vector<int> A, vector<int> B){
    int n = A.size(), m = B.size();
    int a[n], b[m];
    for(int i = 0;i < n;i++)a[i] = A[i] + 1;
    for(int i = 0;i < m;i++)b[i] = B[i] + 1;
    return query(n, m, a, b);
}

void run(int n){
    DSU dsu(n);
    for(int it = 0;it < n - 1;it++){
        map<int, vector<int> > mp;
        for(int i = 0;i < n;i++)mp[dsu.fnd(i)].push_back(i);
        vector<vector<int> > C;
        int ind[n];
        // int T = 0;
        for(auto [a, b]: mp){
            for(auto u: b)ind[u] = C.size();
            C.push_back(b);
        }
        for(int j = 1;j < C.size();j *= 2){
            vector<int> v[2];
            for(int i = 0;i < C.size();i++){
                for(auto u: C[i]){
                    if(j & i)v[1].push_back(u);
                    else v[0].push_back(u);
                }
            }
            if(ask(v[0], v[1])){
                int lo = -1, hi = v[0].size();
                while(hi - lo > 1){
                    int mid = (lo + hi) / 2;
                    vector<int> q;
                    for(int i = 0;i <= mid;i++)q.push_back(v[0][i]);
                    if(ask(q, v[1]))hi = mid;
                    else lo = mid;
                }
                int x = v[0][hi];

                v[0] = {x};
                vector<int> nv;
                for(auto u: v[1]){
                    bool yes = 1;
                    for(int k = 1;k < j;k *= 2){
                        bool b1 = ind[x] & k;
                        bool b2 = ind[u] & k;
                        if(b1 != b2)yes = 0;
                    }
                    if(yes)nv.push_back(u);
                }
                v[1] = nv;

                lo = -1, hi = v[1].size();
                while(hi - lo > 1){
                    int mid = (lo + hi) / 2;
                    vector<int> q;
                    for(int i = 0;i <= mid;i++)q.push_back(v[1][i]);
                    if(ask(q, v[0]))hi = mid;
                    else lo = mid;
                }
                int y = v[1][hi];
                setRoad(x + 1, y + 1);
                dsu.upd(x, y);
                break;
            }
        }
    }
}

// signed main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     int t = 1;
//     //  cin>>t;
//     while (t--)orz();
// }   

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp:15:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   15 | const int INF = 1e17;
      |                 ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 0 / 10