[CF] Round #673 (Div. 2) _ 200927

(2020년 10월 4일에 작성한 글입니다.)

 

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

 

A.

제일 작은 걸 계속 copy할때 횟수가 최대이기 때문에

arr에 값을 받고, 정렬하고

두 번째 원소부터 끝까지 (k-arr[i])/arr[0] 값을 더했다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, K;
	int ans;
	int i;

	cin >> T;
	while (T--) {
		cin >> N >> K;
		vector<int> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i];
		}
		sort(arr.begin(), arr.end());

		ans = 0;
		for (i = 1; i < N; i++) {
			ans += (K - arr[i]) / arr[0];
		}

		cout << ans << '\n';
	}

	return 0;
}

​

B.

이걸 풀면서 정말 큰일났다고 느꼈는데

무려 다섯번이나 틀렸다.

내 풀이는 정말 이상하고 별로라 원빈이 풀이를 적자면

T가 홀수면, 두 배열을 홀수들/짝수들로 분리하면 되고

T가 짝수면, 있는지 없는지 찾아서 분리하면 된다...

T가 홀수/짝수일 때로 나누어서 하는 걸 전혀 생각 못했다.

void change(int* flag) {
	if (*flag) {
		*flag = 0;
	}
	else {
		*flag = 1;
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	int N, T;
	int index;
	int flag;
	int i;

	cin >> t;
	while (t--) {
		cin >> N >> T;
		vector<int> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i];
		}

		vector<pair<int, int>> arr2(N);
		for (i = 0; i < N; i++) {
			arr2[i].first = arr[i];
			arr2[i].second = i;
		}
		sort(arr.begin(), arr.end());
		sort(arr2.begin(), arr2.end());

		vector<int> ans(N, -1);
		flag = 0;
		for (i = 0; i < N;) {
			if (ans[arr2[i].second] == -1) {
				int temp = arr2[i].first;
				if (temp * 2 == T) {
					for (; i < N && arr2[i].first == temp; i++) {
						ans[arr2[i].second] = flag;
						change(&flag);
					}
				}
				else {
					for (; i < N && arr2[i].first == temp; i++) {
						ans[arr2[i].second] = flag;
					}
					change(&flag);
				}

				index = lower_bound(arr.begin(), arr.end(), T - temp) - arr.begin();
				if (temp * 2 != T) {
					for (; index < N && temp + arr[index] == T; index++) {
						ans[arr2[index].second] = flag;
					}
				}
			}
			else {
				i++;
			}
		}

		for (i = 0; i < N; i++) {
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

이건 내 코드다..ㅎ

정말 길다..