제출 #231861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231861		Theo830	동굴 (IOI13_cave)	C++17	51 / 100	2092 ms	1664 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef int ll;
long long INF = 1e18+7;
long long MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(long long i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<endl;
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
const long long N = 1e6+5;
vll visit,dist,taken;
vector<vll> adj;
vector<vii> adj2;
priority_queue<ii,vector<ii>, greater<ii> > pq;
ll bit[N][2];
ll siz;
ll res = 0;
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
long long power(long long a,long long b){if(b == 0)return 1;if(b == 1)return a;long long ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
void BITup(ll k, ll x,ll pos){while(k <= siz){bit[k][pos]+=x;k += k & -k;}}
ll BITq(ll k,ll pos){ll s=0;while(k>=1){s+=bit[k][pos];k -= k &-k;}return s;}
struct node{ll lazy,val;}seg[4000000];
struct point{ll x,y;};
void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
void YESNO(ll a){if(!!a){pl("Yes");}else{pl("No");}}
void filesin(void){freopen("tracing.in","r",stdin);}
void filesout(void){freopen("tracing.out","w",stdout);}
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Training
set<ll>exo;
ll cur = 0;
ll u = 0;
int n;
/*
int tryCombination(int arr[]){
    int a = 0;
    f(i,0,n){
        if(arr[i] == 0){
            a++;
        }
        else{
            break;
        }
    }
    if(a == n){
        return -1;
    }
    return a;
}
void answer(int arr[],int a[]){
    return;
    f(i,0,n){
        ps(arr[i]);
    }
    cout<<endl;
    f(i,0,n){
        ps(a[i]);
    }
}
*/
void solve(set<ll>left,set<ll>right,int &sosto,int ans[]){
    int a = tryCombination(ans);
    set<ll>l,r;
    if(a > cur || a == -1){
        if(left.size() == 1){
            ll val;
            for(auto x:left){
                val = x;
            }
            exo.erase(val);
            u = val;
            return;
        }
        ll i = 0;
        for(auto x:left){
            if(i < left.size()/2){
                l.insert(x);
                ans[x] = sosto;
            }
            else{
                r.insert(x);
                ans[x] = (sosto^1);
            }
            i++;
        }
    }
    else{
        if(right.size() == 1){
            ll val;
            for(auto x:right){
                val = x;
            }
            exo.erase(val);
            u = val;
            return;
        }
        ll i = 0;
        for(auto x:right){
            if(i < right.size()/2){
                l.insert(x);
                ans[x] = sosto;
            }
            else{
                r.insert(x);
                ans[x] = (sosto^1);
            }
            i++;
        }
    }
    if(l.size() == 1 && r.empty()){
        ll val;
        for(auto x:l){
            val = x;
        }
        exo.erase(val);
        u = val;
        return;
    }
    if(r.size() == 1 && l.empty()){
        ll val;
        for(auto x:r){
            val = x;
        }
        exo.erase(val);
        u = val;
        return;
    }
    solve(l,r,sosto,ans);
}
void exploreCave(int N){
    int n = N;
    f(i,0,n){
        exo.insert(i);
    }
    int ans[n]={0};
    int ans2[n]={0};
    while(cur < n){
        for(auto x:exo){
            ans[x] = 0;
        }
        int a = tryCombination(ans);
        int sosto;
        if(a > cur || a == -1){
            sosto = 0;
        }
        else{
            sosto = 1;
        }
        ll i = 0;
        set<ll>l,r;
        for(auto x:exo){
            if(i < exo.size()/2){
                l.insert(x);
                ans[x] = sosto;
            }
            else{
                r.insert(x);
                ans[x] = (sosto^1);
            }
            i++;
        }
        if(l.size() == 1 && r.empty()){
            ll val;
            for(auto x:l){
                val = x;
            }
            exo.erase(val);
            u = val;
        }
        else if(r.size() == 1 && l.empty()){
            ll val;
            for(auto x:r){
                val = x;
            }
            exo.erase(val);
            u = val;
        }
        else{
            solve(l,r,sosto,ans);
        }
        ans[u] = sosto;
        ans2[u] = cur;
        cur++;
    }
    answer(ans,ans2);
}
/*
int main(){
    n = 1000;
    exploreCave(n);
}
*/

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

cave.cpp: In function 'void solve(std::set<int>, std::set<int>, int&, int*)':
cave.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i < left.size()/2){
                ~~^~~~~~~~~~~~~~~
cave.cpp:129:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i < right.size()/2){
                ~~^~~~~~~~~~~~~~~~
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:182:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i < exo.size()/2){
                ~~^~~~~~~~~~~~~~
cave.cpp: In function 'void filesin()':
cave.cpp:52:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesin(void){freopen("tracing.in","r",stdin);}
                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cave.cpp: In function 'void filesout()':
cave.cpp:53:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesout(void){freopen("tracing.out","w",stdout);}
                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 0 / 24