제출 #295533

#제출 시각아이디문제언어결과실행 시간메모리
295533eohomegrownapps자리 배치 (IOI18_seats)C++14
0 / 100
4035 ms118080 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; vector<int> r; vector<int> c; vector<set<int>> firstindr; vector<set<int>> firstindc; int h; int w; int n; int INF = 1e9; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { r=R; c=C; n=H*W; h=H;w=W; firstindr.resize(h); firstindc.resize(w); for (int i = 0; i<n; i++){ firstindr[r[i]].insert(i); firstindc[c[i]].insert(i); } //display(minr);display(maxr); //display(minc);display(maxc); } int swap_seats(int a, int b) { firstindr[r[a]].erase(a); firstindr[r[a]].insert(b); firstindr[r[b]].erase(b); firstindr[r[b]].insert(a); firstindc[c[a]].erase(a); firstindc[c[a]].insert(b); firstindc[c[b]].erase(b); firstindc[c[b]].insert(a); /*for (int i = 0; i<h; i++){ cout<<*firstindr[i].begin()<<' '; }cout<<'\n'; for (int i = 0; i<w; i++){ cout<<*firstindc[i].begin()<<' '; }cout<<'\n';*/ swap(r[a],r[b]); swap(c[a],c[b]); int zrloc = -1; int zcloc = -1; for (int i = 0; i<h; i++){ if (*firstindr[i].begin()==0){ zrloc=i;break; } } for (int i = 0; i<w; i++){ if (*firstindc[i].begin()==0){ zcloc=i;break; } } //cout<<zrloc<<' '<<zcloc<<'\n'; vector<pair<int,pair<int,int>>> sortarr; // {index, {{rmin,rmax,cmin,cmax},value}} int prevind = -1; for (int i = zrloc; i<h; i++){ auto iloc = firstindr[i].upper_bound(prevind); if (iloc!=firstindr[i].end()){ prevind=*iloc; sortarr.push_back({*iloc,{1,i}}); } } prevind = -1; for (int i = zrloc; i>=0; i--){ auto iloc = firstindr[i].upper_bound(prevind); if (iloc!=firstindr[i].end()){ prevind=*iloc; sortarr.push_back({*iloc,{0,i}}); } } prevind = -1; for (int i = zcloc; i<w; i++){ auto iloc = firstindc[i].upper_bound(prevind); if (iloc!=firstindc[i].end()){ prevind=*iloc; sortarr.push_back({*iloc,{3,i}}); } } prevind = -1; for (int i = zcloc; i>=0; i--){ auto iloc = firstindc[i].upper_bound(prevind); if (iloc!=firstindc[i].end()){ prevind=*iloc; sortarr.push_back({*iloc,{2,i}}); } } sortarr.push_back({n,{-1,-1}}); sort(sortarr.begin(),sortarr.end()); int curind = sortarr[0].first; int rmin = INF; int rmax = -INF; int cmin = INF; int cmax = -INF; int tot = 0; for (int i = 0; i<sortarr.size(); i++){ auto p = sortarr[i]; //cout<<p.first<<' '<<p.second.first<<' '<<p.second.second<<'\n'; if (p.first!=curind){ //cout<<"at "<<curind<<": rmin "<<rmin<<" rmax "<<rmax<<" cmin "<<cmin<<" cmax "<<cmax<<'\n'; int nextind = sortarr[i].first; int totval = (rmax-rmin+1)*(cmax-cmin+1); // does totval apply between curind+1 and nextind+1? if (curind+1<=totval&&totval<=nextind+1){ tot++; } curind=p.first; } if (p.second.first==-1){break;} if (p.second.first==0){ rmin=min(rmin,p.second.second); } else if (p.second.first==1){ rmax=max(rmax,p.second.second); } else if (p.second.first==2){ cmin=min(cmin,p.second.second); } else if (p.second.first==3){ cmax=max(cmax,p.second.second); } else { assert(1==0); } } return tot; }

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

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for (int i = 0; i<sortarr.size(); i++){
      |                  ~^~~~~~~~~~~~~~~
#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...