Submission #987896

#TimeUsernameProblemLanguageResultExecution timeMemory
987896kachim2Arranging Shoes (IOI19_shoes)C++17
10 / 100
1032 ms138840 KiB
#include "shoes.h" #include <climits> #include <vector> #include <queue> #include <iostream> long long count_swaps(std::vector<int> s) { std::vector<int> pos(s.size(), INT_MIN); std::vector<int> spos(s.size()); std::vector<int> rpos(s.size()); for (int i = 0; i < s.size(); i++) { spos[i] = i; } for (int i = 0; i < s.size(); i++) { rpos[i] = i; } std::queue<int> qm[100007]; std::queue<int> qp[100007]; for (int i = 0; i < s.size(); i++) { if (s[i] < 0) { if (qp[-s[i]].empty()) { qm[-s[i]].push(i); } else { auto x = qp[-s[i]].front(); qp[-s[i]].pop(); pos[i] = x; } } else { if (qm[s[i]].empty()) { qp[s[i]].push(i); } else { auto x = qm[s[i]].front(); qm[s[i]].pop(); pos[i] = x; } } } long count = 0; for (int i = 0; i < s.size(); i++) { if (pos[i] >= 0) { int wp = s[spos[i]] > 0 ? spos[pos[i]] + 1 : spos[pos[i]]; count+=spos[i]-wp; for (int j = wp; j < spos[i]; j++) { spos[rpos[j]]++; rpos[spos[j]] = j; } spos[i] = wp; rpos[wp] = i; } } /* for (auto i : spos) { std::cerr << i << ' '; } std::cerr << '\n'; for (auto i : rpos) { std::cerr << i << ' '; } std::cerr << '\n'; for (auto i : pos) { std::cerr << i << ' '; }*/ return count; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:10:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
shoes.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
shoes.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
shoes.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
#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...