제출 #138710

#제출 시각아이디문제언어결과실행 시간메모리
138710almogwald커다란 상품 (IOI17_prize)C++14
97.41 / 100
58 ms508 KiB
#include <utility> #include <algorithm> #include <math.h> #include <vector> #include <set> #include <iostream> #include "prize.h" #define fori(i,n) for(int i=0;i<n;i++) #define forib(i,n) for(int i=n-1;i>=0;i--) #define maxl 10000000000 typedef long long lol; using namespace std; typedef vector<int> veci; typedef pair<int,int> point; lol sum=0; veci merge(veci a ,veci b){ int i=0,j=0; veci ans; while(i<a.size()&&j<b.size()){ if(a[i]<b[j]){ ans.push_back(a[i++]); sum+=j; }else{ ans.push_back(b[j++]); } } while(i<a.size()){ ans.push_back(a[i++]); sum+=j; } while(j<b.size()){ ans.push_back(b[j++]); } return ans; } veci mergesort(veci a){ if(a.size()==1){ return a; } veci b,c; fori(i,a.size()){ if(i<a.size()/2){ b.push_back(a[i]); }else{ c.push_back(a[i]); } } b=mergesort(b); c=mergesort(c); return merge(b,c); } int find_best(int n) { if(n<5000){ for(int i = 0; i < n; i++) { std::vector<int> res = ask(i); if(res[0] + res[1] == 0) return i; } } int m=0; int s=0;int ss=0; fori(i,500){ vector<int> res = ask(i); if(res[0] + res[1]>m){ m=res[0] + res[1]; ss+=s; s=0; } if(res[0] + res[1]==m){ s++; }else{ ss++; } if(res[0] + res[1] == 0) return i; } vector<pair<point,point>> tos; tos.push_back({{500,n-1},{ss,0}}); while(true){ pair<point,point> cur=tos.back(); tos.pop_back(); int l=cur.first.first; int r=cur.first.second; int ll=cur.second.first; int rr=cur.second.second; if(ll+rr==m){ continue; } int m1=(l+r)/2; int m2=m1; int f=0; while(m2<=r){ vector<int> res = ask(m2++); if(res[0] + res[1] == 0) return m2-1; if(res[0] + res[1] == m){ tos.push_back({{l,m1-1},{ll,res[1]+f}}); tos.push_back({{m2,r},{res[0],rr}}); m2--; break; } f++; } if(m2>r){ tos.push_back({{l,m1-1},{ll,rr+f}}); } } return 0; }

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

prize.cpp: In function 'veci merge(veci, veci)':
prize.cpp:20:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
prize.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
prize.cpp:28:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()){
        ~^~~~~~~~~
prize.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<b.size()){
        ~^~~~~~~~~
prize.cpp: In function 'veci mergesort(veci)':
prize.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
prize.cpp:42:7:
  fori(i,a.size()){
       ~~~~~~~~~~                
prize.cpp:42:2: note: in expansion of macro 'fori'
  fori(i,a.size()){
  ^~~~
prize.cpp:43:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<a.size()/2){
      ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...