Submission #295662

#TimeUsernameProblemLanguageResultExecution timeMemory
295662tzeroArranging Shoes (IOI19_shoes)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <math.h> #include <cassert> #include <cstring> using namespace std; using ll = long long; const int maxn = (int)1e5 + 7; int t[8 * maxn], lz[8 * maxn]; int n; void tle() { while(true) { n--; n++; } } void update(int v, int tl, int tr, int l, int r) { if(tl > r || tr < l) { return; } else if(tl >= l && tr <= r) { lz[v]++; } else { int tm = (tl + tr) / 2; update(2 * v, tl, tm, l, r); update(2 * v + 1, tm + 1, tr, l, r); } } int query(int v, int tl, int tr, int i) { if(tl > i || tr < i) { return -1; } if(lz[v] > 0) { t[v] += lz[v]; if(tl != tr) { lz[2 * v] += lz[v]; lz[2 * v + 1] += lz[v]; } lz[v] = 0; } if(tl == tr) { return t[v]; } else { int tm = (tl + tr) / 2; int ans = query(2 * v, tl, tm, i); if(ans != -1) return ans; ans = query(2 * v + 1, tm + 1, tr, i); return ans; } } ll count_swaps(vector<int> s) { n = (int)s.size(); bool same_size = true; for(int i = 0; i < n; i++) { if(i > 0 && abs(s[i]) != abs(s[i - 1])) same_size = false; } if(n == 2) { if(s[0] < 0) return 0; else return 1; } else if(same_size) { ll move_left = 0, move_right = 0; int found_left = 0, found_right = 0; for(int i = 0; i < n; i++) { if(s[i] < 0) { int pos = found_left * 2; move_left += abs(i - pos); found_left++; } else { int pos = found_right * 2 + 1; move_right += abs(i - pos); found_right++; } } return min(move_left, move_right); } else { memset(t, 0, sizeof(t)); memset(lz, 0, sizeof(lz)); vector<vector<int> > positions(n + 1); for(int i = 0; i < n; i++) { positions[s[i] + (n / 2)].push_back(i); } int ans = 0; for(int position = n - 1; position >= 1; position -= 2) { int right_idx = position + query(1, 0, n - 1, position); if(-s[right_idx] + (n / 2) < 0) tle(); int xx = -s[right_idx] + (n / 2); if(positions[xx].size() == 0) tle(); int left_idx = positions[xx].back(); int closest = left_idx - query(1, 0, n - 1, left_idx); ans += position - closest; if(s[right_idx] > 0) ans--; positions[s[right_idx] + (n / 2)].pop_back(); positions[-s[right_idx] + (n / 2)].pop_back(); update(1, 0, n - 1, left_idx, position); } return ans; } } int main() { int n; scanf("%d", &n); vector<int> _s(2 * n); for(int i = 0; i < n; i++) { scanf("%d", &_s[i]); } printf("%lld\n", count_swaps(_s)); return 0; }

Compilation message (stderr)

shoes.cpp: In function 'int main()':
shoes.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
shoes.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |     scanf("%d", &_s[i]);
      |     ~~~~~^~~~~~~~~~~~~~
/tmp/ccQAillr.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccafdriC.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status