제출 #279508

#제출 시각아이디문제언어결과실행 시간메모리
279508tinjyuAliens (IOI16_aliens)C++14
4 / 100
1 ms416 KiB
#include "aliens.h" #include <iostream> #include <algorithm> using namespace std; struct node{ long long int x,y; }a[1000005]; double dp[1000005],t[1000005][3]; long long int ans,x[1000005],y[1000005],g[1000005]; bool cmp(node a,node b) { if(a.x<b.x)return 1; if(a.x>b.x)return 0; if(a.y>a.y)return 1; return 0; } double check(long long int a,long long int b) { if(t[a][1]==t[b][1])return 99999999999999; return (t[a][0]-t[b][0])/(t[a][1]-t[b][1]); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { for(int i=0;i<n;i++) { a[i].x=r[i]; a[i].y=c[i]; if(a[i].y<a[i].x) { swap(a[i].x,a[i].y); } } sort(a,a+n,cmp); long long int cnt=1; x[1]=a[0].x; y[1]=a[0].y; for(int i=1;i<n;i++) { if(a[i].x>x[cnt] && a[i].y>y[cnt]) { cnt++; x[cnt]=a[i].x; y[cnt]=a[i].y; } else if(a[i].x==x[cnt] && a[i].y>y[cnt]) { x[cnt]=a[i].x; y[cnt]=a[i].y; } } n=cnt; //cout<<n<<endl; //for(int i=1;i<=n;i++)cout<<x[i]<<" "<<y[i]<<endl; system("pause"); if(k>n)k=n; x[0]=0; y[0]=0; double le=0,ri=m*m; while(true) { double mid=(le+ri)/2; int st=0,en=0; //cout<<mid<<endl; dp[1]=0; t[0][0]=(x[1]-1)*(x[1]-1); t[0][1]=x[1]-1; t[0][2]=0; for(int i=1;i<=n;i++) { //cout<<i<<" "<<check(st,st+1)<<" "<<2*y[i]<<endl; while(en>=st+1 && check(st,st+1)<2*y[i]) { st++; } int p=t[st][2]; //cout<<st<<" "<<p<<endl; if(y[p]-x[p+1]+1>0 && p!=0)dp[i]=mid+(double)dp[p]+((y[i]-x[p+1]+1)*(y[i]-x[p+1]+1)-(y[p]-x[p+1]+1)*(y[p]-x[p+1]+1)); else dp[i]=mid+(double)(dp[p]+(y[i]-x[p+1]+1)*(y[i]-x[p+1]+1)); g[i]=g[p]+1; en++; //cout<<dp[i]+(x[i+1]-1)*(x[i+1]-1)<<endl; t[en][0]=dp[i]+(x[i+1]-1)*(x[i+1]-1)-max((long long int)0,y[i]-x[i+1]+1)*max((long long int)0,y[i]-x[i+1]+1); t[en][1]=x[i+1]-1; t[en][2]=i; while(en>=st+2 && check(en,en-2)<check(en-1,en-2)) { en--; t[en][0]=dp[i]+(x[i+1]-1)*(x[i+1]-1)-max((long long int)0,y[i]-x[i+1]+1)*max((long long int)0,y[i]-x[i+1]+1); t[en][1]=x[i+1]-1; t[en][2]=i; } } //cout<<g[n]<<" "<<dp[n]-mid*g[n]<<endl; if(g[n]==k || ri-le<0.00000001)return dp[n]-mid*g[n]+0.00001; if(g[n]<k) { ri=mid; } else le=mid; } }

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

aliens.cpp: In function 'bool cmp(node, node)':
aliens.cpp:14:8: warning: self-comparison always evaluates to false [-Wtautological-compare]
   14 |  if(a.y>a.y)return 1;
      |     ~~~^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:53:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  system("pause");
      |  ~~~~~~^~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...