Submission #57456

#	Time	Username	Problem	Language	Result	Execution time	Memory
57456		leejseo	공장 (KOI13_factory)	C++17	0 / 20	1082 ms	18416 KiB

factory

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

typedef long long lld;

int X[1000001], N;
vector<int> L;
vector<int> temp;


void input(){
	scanf("%d", &N);
	int val;
	for (int i=0; i<N; i++){
		scanf("%d", &val);
		X[val] = i;
	}
	for (int i=0; i<N; i++){
		scanf("%d", &val);
		L.push_back(X[val]);
	}
	L.push_back((int) 1e9);
}

lld merge_sort(int fr, int ed){
	if (ed <= fr+3){
		lld ans = 0;
		for (int i=fr; i<=ed; i++){
			for (int j=fr; j<i; j++){
				if (L[j] > L[i]) ans++;
			}
		}
		for (int i=fr; i<=ed; i++){
			for (int j=fr; j<i; j++){
				if (L[j] > L[i]){
					L[i] ^= L[j];
					L[j] ^= L[i];
					L[i] ^= L[j];
				}
			}
		}
		//printf("%d %d %lld\n", fr, ed, ans);
		return ans;
	}
	int mid = (fr + ed) >>1;
	lld val = merge_sort(fr, mid) + merge_sort(mid+1, ed);
	int lo = 0, hi = mid+1;
	while (lo < mid+1 || hi < ed+1){
		//printf("%d %d\n", lo, hi);
		if (hi > ed || (lo < mid+1 && L[lo] < L[hi])){
			temp.push_back(L[lo++]);
			continue;
		}
		else{
			temp.push_back(L[hi++]);
			val += (lld) mid - lo + 1;
			continue;
		}
	}
	for (int i=0; i<ed-fr+1; i++){
		L[i+lo] = temp[i];
	}
	temp.clear();
	//printf("%d %d %lld\n", fr, ed, val);
	return val;
}

int main(void){
	input();
	//for (int i=0; i<N; i++){
	//	printf("%d ", L[i]);
	//}
	//printf("\n");
	lld ans = merge_sort(0, N-1);
	printf("%lld\n", ans);
}

Compilation message (stderr)

factory.cpp: In function 'void input()':
factory.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
factory.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val);
   ~~~~~^~~~~~~~~~~~
factory.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 2.2
• Subtask 2: 0 / 3.4
• Subtask 3: 0 / 3.8
• Subtask 4: 0 / 4.8
• Subtask 5: 0 / 5.8