제출 #975656

#제출 시각아이디문제언어결과실행 시간메모리
975656attkyArranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; struct Pair { int gauche, droite, nb; void nbDeplacement() { nb = gauche + droite; } bool operator< (Pair other) { return nb < other.nb; } }; int segtree[524288], tailleIntervalle[524288][2]; void define() { for(int loop = 0; loop < 262144; ++loop) { tailleIntervalle[loop+262144][0] = loop+1; tailleIntervalle[loop+262144][1] = loop+1; } for(int loop = 262143; loop >= 1; --loop) { tailleIntervalle[loop][0] = tailleIntervalle[loop*2][0]; tailleIntervalle[loop][1] = tailleIntervalle[loop*2+1][1]; } for(int loop = 1; loop < 524288; ++loop) { segtree[loop] = 0; } } void add(int debut, int pos) { if(tailleIntervalle[pos][0] >= debut) { segtree[pos]++; } else { int gauche = 2*pos, droite = 2*pos+1; if(tailleIntervalle[gauche][1] >= debut) { add(debut, gauche); } if(tailleIntervalle[droite][1] >= debut) { add(debut, droite); } } } int number(int pos) { int nombre = segtree[pos]; if(pos > 1) { nombre += number(pos/2); } return nombre; } int64_t count_swaps(vector<int> S) { int n = S.size()/2; vector<vector<int>> shoeLeft(n); vector<vector<int>> shoeRight(n); for(int loop = 0; loop < S.size(); ++loop) { if(S[loop] > 0) { shoeRight[S[loop]-1].push_back(loop); } else { shoeLeft[-(S[loop])-1].push_back(loop); } } vector<Pair> pair; for(int loop = 0; loop < n; ++loop) { for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) { pair.push_back({shoeLeft[loop][looping], shoeRight[loop][looping], -1}); } } for(int loop = 0; loop < pair.size(); ++loop) { pair[loop].nbDeplacement(); } sort(pair.begin(), pair.end()); long long int nbDeplacement = 0; for(int loop = 0; loop < pair.size(); ++loop) { int g = pair[loop].gauche, d = pair[loop].droite; int change = -1; if(d < g) { change++; } int ng = max(0, g-number(g+262144)); int nd = max(0, d-number(d+262144)); add(g+1, 1); add(d+1, 1); nbDeplacement += ng + nd + change; } return nbDeplacement; }

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

shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int loop = 0; loop < S.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~
shoes.cpp:68:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int looping = 0; looping < shoeLeft[loop].size(); ++looping) {
      |                              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp:72:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int loop = 0; loop < pair.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~~~~
shoes.cpp:77:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pair>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int loop = 0; loop < pair.size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~~~~
#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...