제출 #1030494

#제출 시각아이디문제언어결과실행 시간메모리
1030494enderArranging Shoes (IOI19_shoes)C++17
65 / 100
40 ms4404 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long count_swaps(std::vector<int> s) { if(s.size() > 16){ long long ans = 0; int cl = 0, cr = 0; priority_queue<int, vector<int>, greater<int>> l, r; for(int i = 0; i < s.size(); ++i){ if(s[i] < 0) l.push(i); else r.push(i); } for(int i = 0; i < s.size(); ++i){ if(i%2 == 0){ if(s[i] > 0){ ans += l.top() - i; swap(s[i], s[l.top()]); r.pop(); r.push(l.top()); } l.pop(); }else { if(s[i] < 0){ ans += r.top() - i; swap(s[i], s[r.top()]); l.pop(); l.push(r.top()); } r.pop(); } } return ans; } int n = s.size()/2; vector<int> p; for(const auto &i : s) if(i > 0) p.push_back(i); //for(int i = 1; i <= n; ++i) p.push_back(i); sort(p.begin(), p.end()); long long ans = 1e18; do{ long long cnt = 0; vector<int> curr; // same size as s vector<int> current_s(s.begin(), s.end()); for(int i = 0; i < n; ++i){ curr.push_back(-p[i]); curr.push_back(p[i]); } for(int i = 0; i < s.size(); ++i){ if(i%2 == 0){ // debe ser zapato izquierdo if(current_s[i] == curr[i]) continue; for(int j = i+1; j < s.size(); ++j){ if(current_s[j] == curr[i]){ for(int k = j; k > i; --k){ swap(current_s[k], current_s[k-1]); cnt++; } break; } } }else { // debe ser zapato derecho if(current_s[i] == current_s[i-1] * -1) continue; int target = current_s[i-1] * -1; for(int j = i+1; j < s.size(); ++j){ if(current_s[j] == target){ for(int k = j; k > i; --k){ swap(current_s[k], current_s[k-1]); cnt++; } break; } } } } ans = min(cnt, ans); } while (next_permutation(p.begin(), p.end())); return ans; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < s.size(); ++i){
      |                 ~~^~~~~~~~~~
shoes.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < s.size(); ++i){
      |                 ~~^~~~~~~~~~
shoes.cpp:11:6: warning: unused variable 'cl' [-Wunused-variable]
   11 |  int cl = 0, cr = 0;
      |      ^~
shoes.cpp:11:14: warning: unused variable 'cr' [-Wunused-variable]
   11 |  int cl = 0, cr = 0;
      |              ^~
shoes.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i = 0; i < s.size(); ++i){
      |                  ~~^~~~~~~~~~
shoes.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int j = i+1; j < s.size(); ++j){
      |                     ~~^~~~~~~~~~
shoes.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    for(int j = i+1; j < s.size(); ++j){
      |                     ~~^~~~~~~~~~
#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...