제출 #282595

#제출 시각아이디문제언어결과실행 시간메모리
282595catalystgmaArranging Shoes (IOI19_shoes)C++14
10 / 100
1 ms384 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define pli pair<ll,int> #define pil pair<int,ll> #define fi first #define se second #define inf (INT_MAX/2-1) #define infl (1LL<<60) #define vi vector<int> #define vl vector<ll> #define pb push_back #define sz(a) (int)(a).size() #define all(a) begin(a),end(a) #define y0 y5656 #define y1 y7878 #define y2 y9090 #define aaa system("pause"); #define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa #define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa #define dbgs(x) cerr<<(#x)<<"[stl]: ";for(auto _:x)cerr<<_<<' ';cerr<<'\n',aaa #define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa #define maxn 2000 #include "shoes.h" using namespace std; bool viz[maxn+5]; ll f_la_fel (vi v) { int n = sz(v); auto to_equal = [&n] (vi v, vi to) { vi p1, p2; int i, j, z; for (i = 0; i < n; i++) if (v[i] < 0) p1.pb(i); for (i = 0; i < n; i++) if (to[i] < 0) p2.pb(i); ll ans = 0; for (i = 0; i < n/2; i++) ans += abs(p2[i]-p1[i]); return ans; }; int x = abs(v[0]); vi to1(n, x), to2(n, -x); for (int i = 0; i < n; i += 2) { to1[i] *= -1; to2[i] *= -1; } return min(to_equal(v, to1), to_equal(v, to2)); } ll f1000 (vi v) { int n = sz(v), i, j, z; ll ans = 0; auto cbt = [&n, &v] () { fill(viz, viz+n, 0); for (int i = 0; i < n-1; i++) if (v[i] < 0 && v[i+1] == -v[i]) viz[i] = viz[i+1] = 1; }; vector<vi> ap(n/2+1); for (int _ = 0; _ < n/2; _++) { for (i = 1; i <= n/2; i++) ap[i].clear(); for (i = 0; i < n; i++) ap[abs(v[i])].pb(i); pii best = pii(0, inf); int len = inf; cbt(); for (i = 1; i <= n/2; i++) { int m = sz(ap[i]); ///-x ... x for (j = 0; j < m; j++) if (!viz[ap[i][j]] && v[ap[i][j]] < 0) { z = j+1; while (z < m && (viz[ap[i][z]] || v[ap[i][z]] != i)) z++; if (z < m && ap[i][z] > ap[i][j]+1 && ap[i][z]-ap[i][j]-1 < len) { best = pii(ap[i][j], ap[i][z]); len = ap[i][z]-ap[i][j]-1; } } ///x ... -x for (j = 0; j < m; j++) if (!viz[ap[i][j]] && v[ap[i][j]] > 0) { z = j+1; while (z < m && (viz[ap[i][z]] && v[ap[i][z]] != -i)) z++; if (z < m && ap[i][z]-ap[i][j] < len) { best = pii(ap[i][j], ap[i][z]); len = ap[i][z]-ap[i][j]; } } } if (len == inf) break; while (len--) { swap(v[best.se], v[best.se-1]); swap(viz[best.se], viz[best.se-1]); best.se--; ans++; } } return ans; } ll count_swaps (vi v) { int n = sz(v); if (n == 2) { if (v[0] > v[1]) return 1; return 0; } if (n <= 2000) return f1000(v); return f_la_fel(v); } //int main () { // int n; cin >> n; // int i, j, z; // vi v(n*2); // for (i = 0; i < 2*n; i++) cin >> v[i]; // cout << count_swaps(v); // return 0; //}

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

shoes.cpp: In lambda function:
shoes.cpp:35:12: warning: unused variable 'j' [-Wunused-variable]
   35 |     int i, j, z;
      |            ^
shoes.cpp:35:15: warning: unused variable 'z' [-Wunused-variable]
   35 |     int i, j, z;
      |               ^
#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...