제출 #50024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50024		hamzqq9	코알라 (APIO17_koala)	C++14	57 / 100	111 ms	920 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define M 10000002
#define LOG 20
#define magic 100
#define KOK 350
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

int N,W;
int i1,i2=1;

int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    int R[105];
    int B[105]={0};

    B[0]=1;

    playRound(B,R);

    if(R[0]==1 || R[0]==0) {

        return 0;

    }
    else {

        for(int i=1;i<N;i++) if(!R[i]) return i;

    }

}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    vector<int> v11,v12,v21,v22,v23,v24,v31,v32,v33,v34,v35,v36;

    int B[105]={0};

    int R[105];

    for(int i=0;i<N;i++) B[i]=1;

    playRound(B,R);

    for(int i=0;i<N;i++) {

        if(R[i]>=2) v12.pb(i);
        else v11.pb(i);

    }

    for(int i:v12) B[i]=2;

    for(int i:v11) B[i]=0;

    playRound(B,R);

    for(int i:v12) {

        if(R[i]>=3) {

            v24.pb(i);

        }
        else {

            v23.pb(i);

        }

    }

    for(int i:v11) {

        if(R[i]>=1) {

            v22.pb(i);

        }
        else {

            v21.pb(i);

        }

    }

    memset(B,0,sizeof(B));

    for(int i:v23) B[i]=1;
    for(int i:v24) B[i]=3;

    playRound(B,R);

    for(int i:v24) {

        if(R[i]>=4) v36.pb(i);
        else v35.pb(i);

    }

    for(int i:v23) {

        v34.pb(i);

    }

    for(int i:v22) v33.pb(i);

    for(int i:v21) {

        if(R[i]>=1) v32.pb(i);
        else v31.pb(i);

    }

    memset(B,0,sizeof(B));

    for(int i:v36) B[i]=10;

    playRound(B,R);

    for(int i=0;i<N;i++) if(R[i]>=11) return i;

}

int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    int B[105]={0};
    int R[105];

    int bas=1,son=8;

    memset(B,0,sizeof(B));

    while(bas<=son) {

        B[i1]=B[i2]=orta;

        playRound(B,R);

        int s1=(R[i1]>orta);
        int s2=(R[i2]>orta);

        if(s1&s2) {

            bas=orta+1;

        }
        else if(!(s1^s2)) {

            son=orta-1;

        }
        else {

            if(s1) return 0;
            return 1;

        }

    }
}

int doit(int x,int y) {i1=x;i2=y;return greaterValue(N,W);}

void solve(vector<int> &now) {

    vector<int> l,r;

    if(sz(now)<=1) return ;

    for(int i=0;i<sz(now)/2;i++) l.pb(now[i]);

    for(int i=sz(now)/2;i<sz(now);i++) r.pb(now[i]);

    now.clear();

    solve(l);
    
    solve(r);

    int b1=0,b2=0;

    while(b1<sz(l) || b2<sz(r)) {

        if(b1<sz(l) && (b2==sz(r) || (doit(l[b1],r[b2])))) {

            now.pb(l[b1++]);

        }
        else {

            now.pb(r[b2++]);

        }
 
    }

}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.

        vector<int> all;

        for(int i=0;i<N;i++) all.pb(i);

        ::N=N;
        ::W=W;

        solve(all);

        for(int i=0;i<N;i++) P[all[i]]=i+1;

    }
}

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

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:166:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:207:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 14 / 18
• Subtask 4: 0 / 10
• Subtask 5: 24 / 53