제출 #1056698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056698		jamesbamber	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	604 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;

	vector<int> numid(2*n);
	map<int, vector<int>> nums;
	int ct = 0;
	for(int i=0; i<2*n; i++){
		if(nums.count(s[i]) and nums[s[i]].size() != 0){
			numid[i] = nums[s[i]].back();
			nums[s[i]].pop_back();
		}
		else{
			numid[i] = ct;
			nums[-s[i]].push_back(ct);
			ct++;
		}
	}
	vector<int> perm(n);

	for(int i=0; i<2*n; i++){
		perm[i] = (s[i] > 0)?2*numid[i]+1:2*numid[i];
	}

	vector<int> fw(2*n+1);
	auto add = [&](int i, int x){
		for(; i<fw.size(); i+= i&-i) fw[i] += x;
	};
	auto query = [&](int i){
		int ans = 0;
		for(; i>0; i -= i&-i) ans += fw[i];
		return ans;
	};

	long long ans = 0;
	for(int i=0; i<2*n; i++){
		ans += i - query(perm[i]);
		add(perm[i]+1, 1);
	}
	return ans;
}

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

shoes.cpp: In lambda function:
shoes.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(; i<fw.size(); i+= i&-i) fw[i] += x;
      |         ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15