Submission #1036892

#TimeUsernameProblemLanguageResultExecution timeMemory
1036892DeathIsAweArranging Shoes (IOI19_shoes)C++14
50 / 100
179 ms280868 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define ll long long ll segment[262144]; void update(ll a, ll b) { a += 131072; b += 131072; //if (b >= 262144) { // b = 1/0; //} if (a>=b) { b=1/0; } while (a <= b) { if (a % 2 == 1) {segment[a++]++;} if (b % 2 == 0) {segment[b--]++;} a /= 2; b /= 2; } } ll give(ll a) { ll total = a; //if (a >= 131072) { // return 1/0; //} a += 131072; while (a > 0) { total += segment[a]; a /= 2; } return total; } long long count_swaps(vector<int> s) { for (int i=0;i<262144;i++) { segment[i] = 0; } ll n = s.size(), shift = *max_element(s.begin(), s.end()), ans = 0; vector<deque<ll>> positions(2 * shift + 1); for (int i=0;i<n;i++) { if (shift - s[i] < 0) { return 1/0; } if (shift + s[i] >= positions.size()) { return 1/0; } if (positions[shift - s[i]].empty()) { positions[shift + s[i]].push_back(i); } else { ans += i - give(positions[shift - s[i]][0]); update(positions[shift - s[i]][0], i); if (s[i] > 0) { ans--; } positions[shift - s[i]].pop_front(); } } return ans; }

Compilation message (stderr)

shoes.cpp: In function 'void update(long long int, long long int)':
shoes.cpp:14:6: warning: division by zero [-Wdiv-by-zero]
   14 |   b=1/0;
      |     ~^~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:44:12: warning: division by zero [-Wdiv-by-zero]
   44 |    return 1/0;
      |           ~^~
shoes.cpp:46:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::deque<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (shift + s[i] >= positions.size()) {
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
shoes.cpp:47:12: warning: division by zero [-Wdiv-by-zero]
   47 |    return 1/0;
      |           ~^~
#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...