제출 #597573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597573		FatihSolak	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	505 ms	44696 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct BIT{
	vector<int> bit;
	int n;
	BIT(int size){
		n = size;
		bit.assign(n,0);
	}
	void upd(int pos,int val){
		for(++pos;pos<n;pos += pos & -pos){
			bit[pos] += val;
		}
	}
	int get(int pos){
		int ret = 0;
		for(++pos;pos > 0;pos -= pos & -pos){
			ret += bit[pos];
		}
		return ret;
	}
	int get(int l,int r){
		return get(r) - get(l-1);
	}
};
vector<int> l[N];
vector<int> r[N];
long long solve(vector<int> a,vector<int> b){
	long long ret = 0;
	BIT bt(N);
	map<int,vector<int>> mp;
	int sz = a.size();
	for(int i = sz-1;i>=0;i--){
		mp[a[i]].push_back(i);
	}
	for(int i = 0;i<sz;i++){
		int ps = mp[b[i]].back() + bt.get(mp[b[i]].back()+1,sz);
		ret += ps - i;
		bt.upd(mp[b[i]].back(),1);
		mp[b[i]].pop_back();
	}
	return ret;
}
long long count_swaps(vector<int> s){
	int n = s.size()/2;
	int m = s.size();
	for(int i = 0;i<m;i++){
		if(s[i] < 0)l[-s[i]].push_back(i);
		else r[s[i]].push_back(i);
	}
	vector<pair<int,int>> v;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<l[i].size();j++){
			v.push_back({l[i][j] + r[i][j] + (l[i][j] > r[i][j]),i});
		}
	}
	sort(v.begin(),v.end());
	vector<int> t;
	for(auto u:v){
		t.push_back(-u.second);
		t.push_back(u.second);
	}
	return solve(s,t);
}

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0;j<l[i].size();j++){
      |                 ~^~~~~~~~~~~~

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