| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1052482 | Ahmed57 | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
set<int> rw[10001],cl[10001];
vector<int> r,c;
int h,w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
for(int i = 0;i<H*W;i++){
r.push_back(R[i]);
c.push_back(C[i]);
rw[R[i]].insert(i);
cl[C[i]].insert(i);
}
}
int swap_seats(int a, int b){
rw[r[a]].erase(a);
cl[c[a]].erase(a);
rw[r[b]].erase(b);
cl[c[b]].erase(b);
rw[r[b]].insert(a);
cl[c[b]].insert(a);
rw[r[a]].insert(b);
cl[c[a]].insert(b);
swap(r[a],r[b]);
swap(c[a],c[b]);
vector<array<int,3>> ev;
for(int i = 0;i<h;i++){
ev.push_back({*rw[i].begin(),i,0});
}
for(int i = 0;i<w;i++){
ev.push_back({*cl[i].begin(),i,1});
}
sort(ev.begin(),ev.end());
int mnx = 1e9 , mxx = -1e9;
int mny = 1e9 , mxy = -1e9;
int ans = 1;
int it = 0;
while(it<ev.size()){
int it2 = it;
while(it2<ev.size()&&ev[it2][0]==ev[it][0]){
if(ev[it2][2]==0){
mnx = min(mnx,ev[it2][1]);
mxx = max(mxx,ev[it2][1]);
}else{
mny = min(mny,ev[it2][1]);
mxy = max(mxy,ev[it2][1]);
}
it2++;
}
if(it2==ev.size())break;
if((mxx-mnx+1)*(mxy-mny+1)==ev[it2][0]){
ans++;
}
it = it2;
}
return ans;
}
int main(){
give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1,
1, 2, 2});
cout<<swap_seats(0,5)<<endl;
}