제출 #143862

#제출 시각아이디문제언어결과실행 시간메모리
143862shdutArranging Shoes (IOI19_shoes)C++14
10 / 100
36 ms6008 KiB
#include "shoes.h" #include <vector> #include <map> #include <set> #include <algorithm> #include <iostream> using namespace std; #define inf 1000000007 #define SZ(x) x.size() #define N 100005 #define pb push_back #define x first #define y second #define ls p<<1 #define rs p<<1|1 #define vi std::vector<int> #define rep(i, a, b) for(int i = a; i < b; i++) #define DBG(x) cerr << (#x) << "=" << x << "\n"; std::map<vi, int>f; int check(vi &s){ rep(i, 0, SZ(s)-1){ if(s[i] + s[i+1])return 0; i++; } return 1; } int go(vi &s, int h = 0){ if(f.count(s))return f[s]; //for(auto &x : s)printf("%d ", x); //puts(""); if(check(s))return f[s] = 0; if(h == 25)return inf; int ret = inf; rep(i, 0, SZ(s))if(s[i] < 0){ rep(j, 0, SZ(s)){ if(s[j] + s[i] == 0 && j != i + 1){ vi t; //cerr << s[i] << " " << s[j] << " ..\n"; if(j < i){ rep(k, 0, j)t.pb(s[k]); rep(k, j+1, i+1)t.pb(s[k]); t.pb(s[j]); rep(k, i+1, SZ(s))t.pb(s[k]); ret = std::min(ret, go(t, h+1) + i-j); } else{ rep(k, 0, i+1)t.pb(s[k]); t.pb(s[j]); rep(k, i+1, j)t.pb(s[k]); rep(k, j+1, SZ(s))t.pb(s[k]); ret = std::min(ret, go(t, h+1) + j - i - 1); } } } } return f[s] = ret; } int t[N << 2]; void build(int p, int l, int r){ if(l == r){ t[p] = 1; return; } int m = (l + r) >> 1; build(ls, l, m); build(rs, m+1, r); t[p] = t[ls] + t[rs]; } void upd(int p, int l, int r, int x, int v){ t[p] += v; if(l == r){ return; } int m = (l+r) >> 1; if(x <= m)upd(ls, l, m, x, v); else upd(rs, m+1, r, x, v); } int query(int p, int l, int r, int x, int y){ if(x > y)return 0; if(l >= x && r <= y)return t[p]; int m = (l+r) >> 1, ans = 0; if(x <= m)ans = query(ls, l, m, x, y); if(y > m)ans += query(rs, m+1, r, x, y); return ans; } std::set<pair<int, int>>a, b; long long count_swaps(std::vector<int> s) { int n = s.size(); build(1, 0, n-1); a.clear(); b.clear(); rep(i, 0, n){ if(s[i] < 0)a.insert({-s[i], i}); else b.insert({s[i], i}); } vi vis(n, 0); long long ans = 0; int l = 0, r = n - 1, x, v; while(l <= r){ if(vis[l]){ l++;continue; } if(vis[r]){ r--; continue; } if(s[r] < 0){ x = -s[r]; auto it = b.lower_bound({x, n}); //assert(it != b.begin()); it--; vis[it->y] = 1; v = query(1, 0, n-1, it->y+1, r-1); ans += v + 1; upd(1, 0, n-1, it->y, -1); b.erase(it); a.erase({x, r}); r--; } else if(s[l] < 0){ x = -s[l]; auto it = b.lower_bound({x, 0}); //std::assert(it != b.end()); vis[it->y] = 1; v = query(1, 0, n-1, l+1, it->y-1); ans += v; upd(1, 0, n-1, it->y, -1); b.erase(it); a.erase({x, l}); l++; } else{ x = s[r]; auto it = a.lower_bound({x, n}); //std::assert(it != b.begin()); it--; vis[it->y] = 1; v = query(1, 0, n-1, it->y+1, r-1); ans += v; upd(1, 0, n-1, it->y, -1); b.erase(it); a.erase({x, r}); r--; } } //int res = go(s); //DBG(res) return ans; }

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

shoes.cpp: In function 'int check(std::vector<int>&)':
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
shoes.cpp:24:9:
     rep(i, 0, SZ(s)-1){
         ~~~~~~~~~~~~~                  
shoes.cpp:24:5: note: in expansion of macro 'rep'
     rep(i, 0, SZ(s)-1){
     ^~~
shoes.cpp: In function 'int go(std::vector<int>&, int)':
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:37:5: note: in expansion of macro 'rep'
     rep(i, 0, SZ(s))if(s[i] < 0){
     ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:38:9: note: in expansion of macro 'rep'
         rep(j, 0, SZ(s)){
         ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:46:21: note: in expansion of macro 'rep'
                     rep(k, i+1, SZ(s))t.pb(s[k]);
                     ^~~
shoes.cpp:18:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, a, b) for(int i = a; i < b; i++)
                                       ^
shoes.cpp:53:21: note: in expansion of macro 'rep'
                     rep(k, j+1, SZ(s))t.pb(s[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...