제출 #724958

#제출 시각아이디문제언어결과실행 시간메모리
724958dooompyArranging Shoes (IOI19_shoes)C++17
30 / 100
92 ms21276 KiB
#include "bits/stdc++.h" #include "shoes.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; map<int, vector<int>> m; vector<pair<int, int>> pairs; int bit[300005]; void add(int p, int v) { p++; for (int i = p; i < 300005; i+= i & -i) bit[i] += v; } ll res(int p) { p++; ll sum = 0; for (; p; p -= p & -p) { sum += bit[p]; } return sum; } long long count_swaps(vector<int> s) { for (int i = 0; i < s.size(); i++) { m[s[i]].push_back(i); } ll ans = 0; for (int i = 1; i <= s.size(); i++) { for (int j = 0; j < m[i].size(); j++) { int x = m[i][j], y = m[-i][j]; if (x < y) ans++; else swap(x, y); pairs.push_back({x, y}); } } for (int i = 0; i < s.size(); i++) add(i, 1); for (auto [a, b] : pairs) { add(a, -1); add(b, -1); ans += res(b); } return ans; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
shoes.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 1; i <= s.size(); i++) {
      |                     ~~^~~~~~~~~~~
shoes.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 0; j < m[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
shoes.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < s.size(); i++) add(i, 1);
      |                     ~~^~~~~~~~~~
#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...