Submission #537940

#	Time	Username	Problem	Language	Result	Execution time	Memory
537940		perchuts	Jousting tournament (IOI12_tournament)	C++17	0 / 100	32 ms	12220 KiB

tournament

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int bit[maxn], idx[maxn], N, mxpower, best, indbest, rk;
bool can[maxn];

struct node{
    int mx, ind, mxind, mnind, resp;
    vector<int>adj;
};

void update(int x){
    while(x<=N)bit[x]--, x += x&(-x);
}

int query(int x){
    int ans = 0;
    int mask = 0,tmp = mxpower, sum = 0;
    while(tmp>=0){
        if((mask|(1<<tmp))<=N&&sum + bit[mask|(1<<tmp)]<x)mask|=(1<<tmp), sum += bit[mask];
        --tmp;
    }

    return mask+1;
}

node nodes[2*maxn];

ii dfs(int u){
    can[u] = 1;
    if(u<=N)return {nodes[u].mx>rk,1};
    int lvl = 0, qnt = 0, resp = -1;
    for(auto v:nodes[u].adj){
        ii cur = dfs(v);
        can[u]&=can[v];
        if(cur.first==1&&v>N)resp = nodes[v].resp;
        ckmax(nodes[u].mxind,nodes[v].mxind);ckmin(nodes[u].mnind,nodes[v].mxind);
        qnt += cur.first;ckmax(lvl,cur.second);
        if(ckmax(nodes[u].mx,nodes[v].mx))nodes[u].ind = nodes[v].ind;
    }
    // cout<<u<<" "<<can[u]<<" "<<lvl<<" "<<qnt<<" "<<resp<<endl;
    // cout<<nodes[u].mnind<<" "<<nodes[u].mxind<<" "<<nodes[u].mx<<" "<<nodes[u].ind<<endl;
    if(can[u]){
        if(qnt>1||(qnt==1&&nodes[u].ind!=nodes[u].mxind))can[u] = 0;
        if(can[u]){
            if(resp!=-1)nodes[u].resp = resp;
            else nodes[u].resp = nodes[u].mnind;
            if(ckmax(best,lvl))indbest = nodes[u].resp;
        }
    }
    return {qnt,lvl+1};
}


int GetBestPosition(int n, int c, int R, int *k, int *s, int *e){
    //construir uma arvore representando todas as justas
    //depois de construir a arvore, o problema vira uma simples tree dp
    N = n, rk = R;
    while((1<<mxpower)<=n)++mxpower;
    mxpower--;
    for(int i=1;i<=n;++i)bit[i] = i&(-i), idx[i] = i, nodes[i].mx = k[i-1], nodes[i].ind = nodes[i].mxind = nodes[i].mnind = i-1;
    for(int i=1;i<=c;++i){
        vector<int>v;
        int l = s[i-1]+1, r = e[i-1]+1;
        for(int j=l;j<=r;++j)v.pb(query(j));
        for(auto x:v){
            nodes[n+i].adj.pb(idx[x]);
            if(x!=v[0])update(x);
        }
        idx[v[0]] = n+i;    
        nodes[n+i].mnind = inf;
    }
    dfs(n+c);
    // for(int i=1;i<=n+c;++i){
    //     cout<<"neighbors of "<<i<<endl;
    //     for(auto x:nodes[i].adj)cout<<x<<" ";
    //     cout<<endl;
    //     cout<<"min index is "<<nodes[i].mnind<<endl;
    //     cout<<"max is "<<nodes[i].mx<<" "<<nodes[i].ind<<endl;
    //     cout<<endl;
    // }
    return indbest;
}
// int k[maxn],s[maxn],e[maxn];
// int main(){_
//     int n,c,r;cin>>n>>c>>r;
//     for(int i=0;i<n-1;++i)cin>>k[i];    
//     for(int i=0;i<c;++i)cin>>s[i];    
//     for(int i=0;i<c;++i)cin>>e[i];  
    
//     cout<<GetBestPosition(n,c,r,k,s,e)<<endl;
// }

Compilation message (stderr)

tournament.cpp: In function 'int query(int)':
tournament.cpp:33:9: warning: unused variable 'ans' [-Wunused-variable]
   33 |     int ans = 0;
      |         ^~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51