제출 #1314328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314328		ulvix	CONSUL (info1cup19_consul)	C++20	100 / 100	12 ms	332 KiB

consul

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "grader.h"
#ifdef ULVI
    #include "debug.hpp"
#else
    #define db(...)
    #define dbv(v)
    #define line()
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define enld endl
using namespace std;
using namespace __gnu_pbds;
typedef int ll;
typedef pair<ll,ll> pll;
const ll sz=2e5+100;
const ll lg=20;
const ll mod=1e9+7;
const ll inf=1e18;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(int n)
{
    if(n<=50){
        map<ll,ll> mp;
        for(ll i=1;i<=n;i++) mp[kth(i)]++;
        for(auto [o,p]:mp){
            if(p>n/3){
                say_answer(o);
                return;
            }
        }
        say_answer(-1);
        return;
    }
    uniform_int_distribution<ll> dist(1,n); 
    for(ll i=0;i<30;i++){
        ll d=kth(dist(rng));
        if(cnt(d)>n/3){
            say_answer(d);
            return;
        }
    }
    say_answer(-1);
}

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

consul.cpp:26:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   26 | const ll inf=1e18;
      |              ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 65 / 65