Submission #150530

# Submission time Handle Problem Language Result Execution time Memory
150530 2019-09-01T08:35:41 Z 이 대회 미분 되나요?(#3668, wookje, edenooo, jms100300) King of Chairs (FXCUP4_chairs) C++17
Compilation error
0 ms 0 KB
#include <stdio.h>
#include <stdlib.h>
#include "king.h"
#include "vassal.h"

static int N, chk[101010];
static std::vector<int> W, C;

static void my_assert(int TF, const char* message){
	if(!TF){ puts(message); exit(0); }
}

int main(){
	my_assert(scanf("%d", &N) == 1, "Error: Invalid Input");
	my_assert(1 <= N && N <= 100000, "Error: Invalid Input");

	W.resize(N);
	for(int i = 0; i < N; i++){
		my_assert(scanf("%d", &W[i]) == 1, "Error: Invalid Input");
		my_assert(1 <= W[i] && W[i] <= 1000000, "Error: Invalid Input");
	}

	C.resize(N);
	for(int i = 0; i < N; i++){
		my_assert(scanf("%d", &C[i]) == 1, "Error: Invalid Input");
		my_assert(1 <= C[i] && C[i] <= 1000000, "Error: Invalid Input");
		if(i) my_assert(C[i-1] <= C[i], "Error: Invalid Input");
	}

	long long num = SendInfo(W, C);
	my_assert(0 <= num && num < (1ll << 60), "Wrong[1] : Invalid Number");

	int chair_cnt = 0;
	Init(num, C);
	for(int i = 0; i < N; i++){
		int ci = Maid(W[i]);
		my_assert(-1 <= ci && ci < N, "Wrong[2] : Invalid Chair Number");
		my_assert(-1 == ci || !chk[ci], "Wrong[2] : Invalid Chair Number");
		my_assert(-1 == ci || W[i] <= C[ci], "Wrong[2] : Invalid Chair");
		chk[ci] = 1;
		if(ci>=0) chair_cnt++;
	}

	printf("Correct\n%d\n", chair_cnt);
	return 0;
}
#include "vassal.h"
#include<vector>
#include<algorithm>
using namespace std;

#define SZ 1'000'000

long long BB;
int NN;
int seg[2100000];
vector<int> x[1000101];

int Update(int idx, int val, int n, int l, int r)
{
	if (r < idx || idx < l) return seg[n];
	if (l == r) return seg[n] += val;
	int mid = l + r >> 1;
	return seg[n] = Update(idx, val, n * 2, l, mid) + Update(idx, val, n * 2 + 1, mid + 1, r);
}

int Query(int L, int R, int n, int l, int r)
{
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return seg[n];
	int mid = l + r >> 1;
	return Query(L, R, n * 2, l, mid) + Query(L, R, n * 2 + 1, mid + 1, r);
}

int Kth(int k, int n, int l, int r)
{
	if (l == r) return l;
	int mid = l + r >> 1;
	if (k <= seg[n * 2]) return Kth(k, n * 2, l, mid);
	return Kth(k - seg[n * 2], n * 2 + 1, mid + 1, r);
}

void Init(long long B, std::vector<int> C){
	NN = C.size();
	BB = B;
	for (int i = 0; i < NN; i++)
	{
		Update(C[i], 1, 1, 1, SZ);
		x[C[i]].push_back(i);
	}
	sort(C.begin(), C.end());
	if (B != NN) BB = C[B];
	else BB = 1e9;
}

int Maid(int W){
	if (W > BB) return -1;
	if (Query(W, SZ, 1, 1, SZ) == 0) return -1;
	int cnt = Query(0, W - 1, 1, 1, SZ) + 1;
	int idx = Kth(cnt, 1, 1, SZ);
	int ret = x[idx].back();
	Update(idx, -1, 1, 1, SZ);
	x[idx].pop_back();
	return ret;
}

Compilation message

/tmp/cc5KbhUQ.o: In function `main':
grader_k.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccTMKLXr.o:king.cpp:(.text.startup+0x0): first defined here
/tmp/ccTMKLXr.o: In function `main':
king.cpp:(.text.startup+0x14c): undefined reference to `SendInfo(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
king.cpp:(.text.startup+0x19b): undefined reference to `Init(long long, std::vector<int, std::allocator<int> >)'
king.cpp:(.text.startup+0x218): undefined reference to `Maid(int)'
/tmp/cc5KbhUQ.o: In function `main':
grader_k.cpp:(.text.startup+0x14c): undefined reference to `SendInfo(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status

vassal.cpp: In function 'int Update(int, int, int, int, int)':
vassal.cpp:17:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
vassal.cpp: In function 'int Query(int, int, int, int, int)':
vassal.cpp:25:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
vassal.cpp: In function 'int Kth(int, int, int, int)':
vassal.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~