제출 #1336891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336891		hyyh	Arranging Shoes (IOI19_shoes)	C++20	컴파일 에러	0 ms	0 KiB

shoes

#include "shoes.h"
#include <math.h>
#include <vector>
#include <map>
#include <iostream>
#include <stack>
#include <queue>
#include <bitset>
#include <unordered_map>

using namespace std;

#define endl '\n'
using ll = long long;

int const N = 1e5+10;

int si;

int segment[4*N];
bitset<N> used(0);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void update(int n, int val){
	for(;n <= si;n += n&-n) segment[n] += val;
}

int sum(int n){
	int sum = 0;
	for(;n > 0;n -= n&-n) sum += segment[n];
	return sum;
}

long long count_swaps(std::vector<int> s) {
	unordered_map<int,queue<int>,custom_hash> mp;
	int n = s.size();
	si = pow(2,ceil(log2(n)));
	for(int i{1};i <= n;i++){
		update(i,1);
	}
	for(int i{1};i <= n;i++){
		mp[s[i-1]].push(i);
	}
	// for(int i{1};i <= si;i++) cout << segment[i] << " ";
	// cout << endl;
	ll ans = 0;
	for(int i{1};i <= n;i++){
		if(used[i]) continue;
		int tar = mp[-s[i-1]].front();mp[-s[i-1]].pop();mp[s[i-1]].pop();
		//cout << tar << " " << i << endl;
		used[tar] = 1;
		used[i] = 1;
		//for(int i{1};i <= si;i++) cout << segment[i] << " ";
		//cout << endl;
		//cout << tar << endl;
		update(tar,-1);
		update(i,-1);
		ans += sum(tar)+(s[i-1]>0);
	}
	return ans;
}

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

shoes.cpp:24:12: error: 'uint64_t' does not name a type
   24 |     static uint64_t splitmix64(uint64_t x) {
      |            ^~~~~~~~
shoes.cpp:10:1: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
    9 | #include <unordered_map>
  +++ |+#include <cstdint>
   10 | 
shoes.cpp:32:23: error: 'uint64_t' has not been declared
   32 |     size_t operator()(uint64_t x) const {
      |                       ^~~~~~~~
shoes.cpp: In member function 'size_t custom_hash::operator()(int) const':
shoes.cpp:33:22: error: 'uint64_t' does not name a type
   33 |         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      |                      ^~~~~~~~
shoes.cpp:33:22: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
shoes.cpp:34:31: error: 'FIXED_RANDOM' was not declared in this scope
   34 |         return splitmix64(x + FIXED_RANDOM);
      |                               ^~~~~~~~~~~~
shoes.cpp:34:16: error: 'splitmix64' was not declared in this scope
   34 |         return splitmix64(x + FIXED_RANDOM);
      |                ^~~~~~~~~~