제출 #1364278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364278		mythofys	Kirameki of Revue (KAISTRUN26SPRING_E)	C++20	100 / 100	740 ms	72768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define inf 4000000000000000000
#define mod 998244353
#define siz 524288

set < pair < ll, ll > > s;
priority_queue < pair < ll, ll > > pq;
ll a[200005],v[200005],ncnt = 1;

struct Node
{
    ll v,idx;
};

struct Tree
{
    ll left = 2000001,right = 2000001,sz = 0;
    vector < ll > e;
}trie[2000005];

void update(ll node,ll v,ll idx,ll cnt)
{
    if(cnt == -1)
    {
        //printf("%lld\n",node);
        trie[node].e.push_back(idx);
        trie[node].sz++;
        return;
    }
    if(v & (1LL<<cnt))
    {
        if(trie[node].left == 2000001)trie[node].left = ncnt++;
        update(trie[node].left,v,idx,cnt-1);
        trie[node].sz = trie[trie[node].left].sz + trie[trie[node].right].sz;
    }
    else
    {
        if(trie[node].right == 2000001)trie[node].right = ncnt++;
        update(trie[node].right,v,idx,cnt-1);
        trie[node].sz = trie[trie[node].left].sz + trie[trie[node].right].sz;
    }
}

ll query(ll node,ll v,ll cnt,ll nv)
{
    if(cnt == -1)return trie[node].sz;
    ll ret = 0;
    if(nv & (1LL<<cnt))
    {
        if(v & (1LL<<cnt))ret += trie[trie[node].left].sz;
        else ret += trie[trie[node].right].sz;
        if(v & (1LL<<cnt))return ret + query(trie[node].right,v,cnt-1,nv);
        else return ret + query(trie[node].left,v,cnt-1,nv);
    }
    if(v & (1LL<<cnt))return query(trie[node].left,v,cnt-1,nv);
    else return query(trie[node].right,v,cnt-1,nv);
}

bool can(ll mid,ll n,ll k)
{
    ll i,nans = 0;
    for(i=1;i<=n;i++)
    {
        nans += query(0,a[i],31,mid) - 1;
    }
    return nans >= 2 * k;
}

ll bs(ll s,ll e,ll n,ll k)
{
    if(s == e)return s;
    ll mid = (s+e)/2;
    if(can(mid,n,k))return bs(s,mid,n,k);
    return bs(mid+1,e,n,k);
}

int main()
{
    ll i,j,k,n,m,ans = 0;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        update(0,a[i],i,31);
        v[i] = 1;
    }
    printf("%lld",bs(0,(1LL<<31LL),n,m));
}

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

Main.cpp: In function 'int main()':
Main.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

• 서브태스크 1: 5 / 5
• 서브태스크 2: 20 / 20
• 서브태스크 3: 35 / 35
• 서브태스크 4: 40 / 40