[CF] Round #569 (Div. 2) _ 210514

https://codeforces.com/contest/1180

Dashboard - Codeforces Round #569 (Div. 2) - Codeforces

 

학회 코포 스터디에서 한 버추얼 콘테스트

A.
수학 문제

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n; cin >> n;
	cout << 1 + 2 * n * (n - 1) << ENDL;
	return 0;
}

B.
곱이 최대가 되려면 우선 모든 수를 곱한 결과가 양수여야 할 것이다.
부호는 일단 무시하면 a := -a - 1의 작업을 할 때 절댓값이 커지는 경우는 a >= 0일때이다.
그러므로 우선 값이 0 이상이면 -a - 1의 작업을 해준다.

만약 전체 수의 개수가 짝수개이면 모든 수의 절댓값이 최대인 상태에서, 그것들의 곱이 양수이므로 이 경우가 답이 된다.
그러나 홀수개이면 곱이 음수가 되는데, 이를 처리하기 위해 하나의 수에 a := -a - 1 작업을 해야 한다.
다른 수들을 모두 곱한 결과는 양수이고, 하나의 수에 a := -a - 1 작업을 한 결과도 0 이상이다.
그러므로 부호는 고려할 필요 없이 -a - 1의 값이 최대인 인덱스(a가 가장 작은 곳)의 값에 a := -a - 1의 연산을 해주면 된다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<int> arr(n);
	int maxIdx = -1;
	int maxNum = -1;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] >= 0) {
			arr[i] = -arr[i] - 1;
		}
		
		if (maxNum < -arr[i] - 1) {
			maxNum = -arr[i] - 1;
			maxIdx = i;
		}
	}
	
	if (n % 2 == 1) {
		arr[maxIdx] = maxNum;
	}

	for (int i = 0; i < n; i++) {
		cout << arr[i] << ' ';
	}
	cout << ENDL;

	return 0;
}

C.
deque의 맨 앞 두 수를 각각 A, B라고 할 때
A > B이면 A는 앞에, B는 뒤에 값을 push
A <= B이면 B를 앞에, A는 뒤에 push

후자의 경우는 그냥 deque의 앞에 있는 값을 뒤로 push하는 것이 된다.
그리고 후자의 경우가 반복되다가 deque의 맨 앞에 가장 큰 값이 나타나면 deque의 맨 앞에는 항상 최댓값이 있게 되고, 나머지 값들이 순서대로 반복적으로 나타난다.
그러므로 맨 앞에 최댓값이 나올 때까지의 횟수를 구해두고, 그 이후는 주기를 이용해 결과를 구하면 된다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	ll q; cin >> q;
	deque<int> deq;
	int maxNum = -1;
	for (int i = 0; i < n; i++) {
		int temp; cin >> temp;
		deq.push_back(temp);
		maxNum = max(maxNum, temp);
	}

	vector<pair<int, int>> ans;
	while (1) {
		int a, b;
		a = deq.front(); deq.pop_front();
		b = deq.front(); deq.pop_front();
		ans.push_back({ a, b });
		if (a > b) {
			deq.push_front(a);
			deq.push_back(b);
		}
		else {
			deq.push_front(b);
			deq.push_back(a);
		}

		if (deq.front() == maxNum) {
			break;
		}
	}

	deq.pop_front();
	vector<int> leftover;
	while (!deq.empty()) {
		leftover.push_back(deq.front());
		deq.pop_front();
	}

	while (q--) {
		ll k; cin >> k; k--;
		if (k < ans.size()) {
			cout << ans[k].first << ' ' << ans[k].second << ENDL;
		}
		else {
			k -= ans.size();
			k %= leftover.size();
			cout << maxNum << ' ' << leftover[k] << ENDL;
		}
	}
	

	return 0;
}