답안 #249090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249090 2020-07-14T10:06:32 Z leaked Poklon (COCI17_poklon7) C++14
72 / 120
1000 ms 91384 KB
#include<bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cout << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cout << endl; }
eni(!=) cout << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
//#define sz(x) (ll)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
void binary(ll val,int to) {for(int i=0;i<to;i++) cerr<<(pw(i) & val ? 1 : 0); cerr<<endl;}
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={1,0,-1,0};
const ll ty[4]={0,1,0,-1};
const char rev_to[4]={'E','W','N','S'};
const char o[4]={'S','P','R'};
const int N=2e6+1;
const int M=1e9+7;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> st;
void bad(){
    cout<<-1;
    exit(0);
}
pii mx[N];
int aa[N][2];
string lol[N];
map<int,int>sz;
pii to(pii a,pii b){
    if(sz[a.f]+a.s<sz[b.f]+b.s) return {b.f,b.s+1};
    else if(sz[a.f]+a.s>sz[b.f]+b.s) return {a.f,a.s+1};
    else{
        int f=max(0,sz[a.f]-sz[b.f]),s=max(0,-sz[a.f]+sz[b.f]);
        if((a.f)*pw(s)<b.f*(pw(f))) return {b.f,b.s+1};
        else if((a.f)*pw(s)>b.f*(pw(f))) return {a.f,a.s+1};
        else{
            if(sz[a.f]>sz[b.f]) return {b.f,b.s+1};
            else return {a.f,a.s+1};
        }
    }
}
pii dfs(int v){
    vector<pii>ts(2);
    for(int i=0;i<2;i++){
        if(aa[v][i]<0 ){
            ts[i]={-aa[v][i],0};
        }
        else{
            ts[i]=dfs(aa[v][i]);
        }
    }
    ///debug()<<imie(ts)<<imie(v);
    return to(ts[0],ts[1]);
}
signed main()
{
    fast_io;
    ///TODO :
    int cur=1;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>aa[i][0]>>aa[i][1];
        for(int j=0;j<2;j++){
            if(aa[i][j]<0){
                int ps=-aa[i][j];
                while(ps){
                    sz[-aa[i][j]]++;
                    ps>>=1;
                }
                //cout<<sz[-aa[i][j]];
            }
            else{
                aa[i][j]--;
            }
        }
    }
    //exit(0);
    pii ans=dfs(0);
    bool ok=0;
    for(int j=31;j>=0;j--){
        if(pw(j) & (ans.f)){
            ok=1;
            cout<<1;
        }
        else{
            if(ok)  cout<<0;
        }
    }
    for(int j=0;j<ans.s;j++) cout<<0;
    return 0;
}
/*
*/

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:120:9: warning: unused variable 'cur' [-Wunused-variable]
     int cur=1;
         ^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 62976 KB Output isn't correct
2 Incorrect 33 ms 62976 KB Output isn't correct
3 Correct 33 ms 62976 KB Output is correct
4 Correct 35 ms 62976 KB Output is correct
5 Correct 33 ms 62968 KB Output is correct
6 Correct 34 ms 62968 KB Output is correct
7 Correct 33 ms 62976 KB Output is correct
8 Correct 33 ms 62976 KB Output is correct
9 Correct 34 ms 62976 KB Output is correct
10 Correct 34 ms 62976 KB Output is correct
11 Correct 51 ms 63864 KB Output is correct
12 Correct 54 ms 63864 KB Output is correct
13 Correct 136 ms 67320 KB Output is correct
14 Correct 254 ms 71700 KB Output is correct
15 Incorrect 256 ms 68444 KB Output isn't correct
16 Execution timed out 1031 ms 89468 KB Time limit exceeded
17 Execution timed out 1100 ms 90872 KB Time limit exceeded
18 Execution timed out 1096 ms 88568 KB Time limit exceeded
19 Execution timed out 1092 ms 90872 KB Time limit exceeded
20 Execution timed out 1103 ms 91384 KB Time limit exceeded