제출 #425719

#제출 시각아이디문제언어결과실행 시간메모리
425719ngraceAliens (IOI16_aliens)C++14
0 / 100
18 ms460 KiB
#include "aliens.h" #include <vector> #include <iostream> #include <utility> #include <algorithm> #include <set> #include <limits.h> using namespace std; #define v vector #define pii pair<int,int> #define fi first #define se second long long area(int r, int l){ return (r-l+1)*(r-l+1); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { if(k==1){ long long low=LLONG_MAX; long long high=0; for(int i=0;i<n;i++){ if(r[i]<low) low=r[i]; if(r[i]>high) high=r[i]; if(c[i]<low) low=c[i]; if(r[i]>high) high=c[i]; } return area(high,low); } else if(k==n && m<=100){//sub 1 v<v<bool>> squares(m,v<bool>(m,false)); for(int i=0;i<n;i++){ int low=min(r[i],c[i]); int high=max(r[i],c[i]); for(int a=low;a<=high;a++){ for(int b=low;b<=high;b++){ squares[a][b]=true; } } } long long out=0; for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ out+=squares[i][j]; } } return out; } else{//assume sub 2 //as all along diagonal can do dp with n^3 set<pii> pos; for(int i=0;i<n;i++) pos.insert({min(r[i],c[i]), max(r[i],c[i])}); while(pos.size()>k){ long long extra=LLONG_MAX; pii one; pii two; for(pii it:pos){ for(pii pt:pos){ if(it!=pt){ if(pt.fi>=it.fi){ if(pt.fi<=it.se && pt.se<=it.se){ one=it; two=pt; extra=0; break; } else if(pt.fi<=it.se){ long long cur=area(pt.se,it.fi); cur-= area(it.se,it.fi); cur-= area(pt.se,pt.fi); cur+= area(it.se,pt.fi); if(cur<extra){ extra=cur; one=it; two=pt; } } else{ long long cur=area(pt.se,it.fi); cur-= area(it.se,it.fi); cur-= area(pt.se,pt.fi); if(cur<extra){ extra=cur; one=it; two=pt; } } } } if(extra==0) break; } if(extra==0) break; } pii newSquare={min(one.fi,two.fi),max(one.se,two.se)}; pos.erase(one); pos.erase(two); pos.insert(newSquare); } v<v<bool>> squares(m,v<bool>(m,false)); for(pii it:pos){ int low=it.fi; int high=it.se; for(int a=low;a<=high;a++){ for(int b=low;b<=high;b++){ squares[a][b]=true; } } } long long out=0; for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ out+=squares[i][j]; } } return out; } }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:55:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while(pos.size()>k){
      |               ~~~~~~~~~~^~
#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...