| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 306156 | richyrich | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
set<pair<ll, ll>> left_shoes;
ll n, now,idx, ans;
map<ll, set<ll>>i_r_shoes;
queue<pair<ll, ll>> q;
void shift() {
for(auto c : left_shoes) {
ll IDX = c.first;
if(now <= IDX && IDX <= idx) {
ans++;
q.push({IDX, c.second});
}
}
while(!q.empty()) {
ll a = q.front().first , b = q.front().second;
left_shoes.erase({a, b});
left_shoes.insert({a + 1, b});
q.pop();
}
for(auto &c : i_r_shoes) {
queue<ll> q_p;
for(ll d : c.second) {
if(now <= d && d <= idx) q_p.push(d), ans++;
}
while(!q_p.empty()) {
ll a = q_p.front();
//if(c.second.find(a) != c.second.end()) prllf("YES\n");
c.second.erase(a);
c.second.insert(a+1);
//prllf("now %d %d\n", c.first, a+1);
q_p.pop();
}
}
}
long long count_swaps(std::vector<ll> s) {
n = s.size();
for(ll i = 0; i < n; i++) {
if(s[i] < 0) left_shoes.insert({i, s[i]});
else i_r_shoes[s[i]].insert(i);
}
while(!left_shoes.empty()) {
idx = (*left_shoes.begin()).first;
ll type = (*left_shoes.begin()).second;
left_shoes.erase({idx, type});
shift();
now++;
/*prllf("here --> %d %d \n", type, idx);
for(auto c : left_shoes) {
prllf("%d %d\n", c.second, c.first);
}
for(auto c : i_r_shoes) {
for(auto d : c.second)prllf("%d %d\n", c.first, d);
}
*/
idx = *i_r_shoes[-type].begin();
i_r_shoes[-type].erase(idx);
shift();
now++;/*
prllf("%d\n", ans);
for(auto c : left_shoes) {
prllf("%d %d\n", c.second, c.first);
}
for(auto c : i_r_shoes) {
for(auto d : c.second)prllf("%d %d\n", c.first, d);
}*/
}
return ans;
}