제출 #718106

#제출 시각아이디문제언어결과실행 시간메모리
718106lam코알라 (APIO17_koala)C++14
100 / 100
56 ms336 KiB
#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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...