제출 #718106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718106		lam	코알라 (APIO17_koala)	C++14	100 / 100	56 ms	336 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>
using namespace std;
int n;
int B[110],R[110];
int minValue(int N, int W)
{
    n=N;
    fill_n(B,n,0);
    B[0] = 1;
    playRound(B,R);
    if (R[0]<=1) return 0;
    else for (int i=1; i<n; i++) if (R[i]==0)
        return i;
}

int maxValue(int N, int W)
{
    n=N;
    vector <int> tmp;
    for (int i=0; i<n; i++) tmp.push_back(i);
    while (tmp.size()!=1)
    {
        int val = W / (tmp.size());
        fill_n(B,n,0);
        for (int i:tmp) B[i] = val;
        playRound(B,R);
        tmp.clear();
        for (int i=0; i<n; i++) if (R[i]>val) tmp.push_back(i);
    }
    return tmp[0];
}

int greaterValue(int N, int W)
{
    n=N;
    fill_n(B,n,0);
    int l=1; int r=min(9,W/2);
    while (l<r)
    {
        int mid=(l+r)/2;
        B[0]=B[1]=mid;

        playRound(B,R);
        if (R[0]>mid&&R[1]>mid) l=mid+1;
        else if (R[0]<=mid&&R[1]<=mid) r=mid-1;
        else return (R[0]<R[1]);
    }
    B[0]=B[1]=l;
    playRound(B,R);
    return (R[0]<R[1]);
}

bool comp(int u, int v, int W)
{
    fill_n(B,n,0);
    B[u]=B[v]=W;
    playRound(B,R);
    return R[v]>W;
}

vector <int> msort(vector <int> v, int lx, int rx, int W)
{
    if (lx==rx) return v;
    int mid=(lx+rx)/2;
    vector <int> a,b;
    a.insert(a.end(),v.begin(),v.begin()+(mid-lx+1));
    b.insert(b.end(),v.begin()+(mid-lx+1),v.end());
    a=msort(a,lx,mid,W);
    b=msort(b,mid+1,rx,W);
    vector <int> res;
    int ita,itb;
    ita=itb=0;
    while (ita<a.size()&&itb<b.size())
    {
        if (comp(a[ita],b[itb],W)) res.push_back(a[ita++]);
        else res.push_back(b[itb++]);
    }
    res.insert(res.end(),a.begin()+ita,a.end());
    res.insert(res.end(),b.begin()+itb,b.end());
    return res;
}

void sub4(int N, int W, int *P)
{
    n=N;
    vector <int> tmp;
    for (int i=0; i<n; i++) tmp.push_back(i);
    tmp=msort(tmp,0,n-1,W/2);
    for (int i=0; i<n; i++) P[tmp[i]] = i+1;
}


void dnc(vector <int> v, int lx, int rx, int W, int *P)
{
    if (lx>rx) return;
    if (lx==rx)
    {
        P[v[0]]=lx+1;
        return;
    }
    int mid=(lx+rx)/2;
    int x = min(int(trunc(sqrt(2*(lx+1)))),W/(rx-lx+1));
    fill_n(B,n,0);
    for (int i:v) B[i]=x;
    playRound(B,R);
    vector <int> vl,vr;
    for (int i:v) if (R[i]<=x) vl.push_back(i);
    else vr.push_back(i);
    dnc(vl,lx,lx+vl.size()-1,W,P);
    dnc(vr,rx-vr.size()+1,rx,W,P);
}

void sub5(int N, int W, int *P)
{
    n=N;
    vector <int> tmp;
    for (int i=0; i<n; i++) tmp.push_back(i);
    dnc(tmp,0,n-1,W,P);
}

void allValues(int N, int W, int *P)
{
    if (W==2*N) sub4(N,W,P);
    else
        sub5(N,W,P);
}

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

koala.cpp: In function 'std::vector<int> msort(std::vector<int>, int, int, int)':
koala.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     while (ita<a.size()&&itb<b.size())
      |            ~~~^~~~~~~~~
koala.cpp:75:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     while (ita<a.size()&&itb<b.size())
      |                          ~~~^~~~~~~~~
koala.cpp: In function 'void dnc(std::vector<int>, int, int, int, int*)':
koala.cpp:103:9: warning: unused variable 'mid' [-Wunused-variable]
  103 |     int mid=(lx+rx)/2;
      |         ^~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

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