제출 #705202

#제출 시각아이디문제언어결과실행 시간메모리
705202stoyan_malininArranging Shoes (IOI19_shoes)C++14
0 / 100
260 ms147648 KiB
#include<iostream> #include<cstring> #include<vector> #include<queue> #include<set> using namespace std; const int MAXN = 1e5; struct FenwickTree { int tree[MAXN * 2 + 5]; FenwickTree() { memset(this->tree, 0, sizeof(this->tree)); } void update(int index, int value) { index++; while (index < MAXN*2) { tree[index] += value; index += index&(-index); } } int query(int index) { int sum = 0; index++; while(index>0) { sum += tree[index]; index -= index&(-index); } return sum; } }; FenwickTree *T = new FenwickTree(); queue <int> leftShoes[MAXN + 5], rightShoes[MAXN + 5]; int calcValue(int leftShoeInd, int rightShoeInd) { int val = leftShoeInd + max((rightShoeInd - 1), 0); if (leftShoeInd > rightShoeInd) val++; return val; } int64_t count_swaps(vector <int> s) { set <int> allIndexes; for (int i = 0;i<s.size();i++) { allIndexes.insert(i); if (s[i] < 0) leftShoes[ -s[i] ].push(i); else rightShoes[ s[i] ].push(i); } int64_t answer = 0; for (int index = 0; index < s.size(); index += 2) { int bestIndex = -1; int leftShoeFakeInd, rightShoeFakeInd; bestIndex = abs(s[*allIndexes.begin()]); allIndexes.erase(leftShoes[bestIndex].front()); allIndexes.erase(rightShoes[bestIndex].front()); leftShoeFakeInd = leftShoes[bestIndex].front() - T->query(leftShoes[bestIndex].front()); rightShoeFakeInd = rightShoes[bestIndex].front() - T->query(rightShoes[bestIndex].front()); T->update(leftShoes[bestIndex].front(), 1); T->update(rightShoes[bestIndex].front(), 1); leftShoes[bestIndex].pop(); rightShoes[bestIndex].pop(); answer += calcValue(leftShoeFakeInd, rightShoeFakeInd); } return answer; }

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

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