Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

길이가 $n$인 배열 $a$가 있으며, $i$번째 수는 $a_i$입니다. 또한 각 수에는 점수가 있으며, $i$번째 수의 점수는 $c_i$입니다. Alice와 Bob은 번갈아 가며 턴을 진행하고, Alice가 먼저 시작합니다.

현재 라운드에서 플레이어는 먼저 배열 $a$를 배열 $b$에 복사한 다음, 랜덤 셔플 프로그램을 실행하여 배열 $b$를 무작위로 섞습니다. 구체적으로, 랜덤 셔플 프로그램은 $b$의 순열 중 하나를 동일한 확률로 선택하여 원래 배열 $b$를 그것으로 대체합니다. 현재 배열 $a$의 길이를 $m$이라고 할 때, 플레이어는 $0 \le k \le m$이고 $a[1 \dots k] = b[1 \dots k]$를 만족하는 정수 $k$를 선택한 다음, $a[1 \dots k]$(즉, $a$의 길이가 $k$인 접두사)를 삭제하고 삭제된 수들의 점수를 얻을 수 있습니다. 배열 $a$가 비워지면 게임이 종료됩니다.

전체 과정 동안 배열 $a$와 그 점수 배열 $c$ 자체는 섞이지 않으며, 오직 그 접두사만 제거된다는 점에 유의하세요.

Alice와 Bob은 모두 자신의 점수를 최대화하고 싶어 합니다. Alice는 두 플레이어가 모두 최적의 전략을 채택했을 때 자신의 기댓값 점수가 얼마인지 알고 싶어 합니다.

Alice는 또한 $q$개의 수정 그룹(배열과 점수를 수정함)을 수행했으며, 초기 배열에 대한 답과 각 수정 그룹 이후의 답을 모두 구하기를 원합니다.

입력

첫 번째 줄에는 초기 배열 $a$의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

두 번째 줄에는 초기 배열 $a$를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어집니다.

세 번째 줄에는 배열의 각 수의 점수를 나타내는 $n$개의 정수 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$)이 주어집니다.

다음 줄에는 수정 그룹의 수를 나타내는 정수 $q$ ($0 \le q \le 10$)가 주어집니다.

다음은 $q$개의 수정 그룹을 설명합니다:

각 수정 그룹에 대해, 첫 번째 줄에는 이 그룹의 수정 횟수를 나타내는 $k_i$ ($1 \le k_i \le 10^5$)가 주어집니다.

다음 $k_i$개의 줄에는 각각 $a_{p_j}$를 $x_j$로 수정하고 $c_{p_j}$를 $y_j$로 수정함을 나타내는 세 정수 $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$)가 주어집니다.

$p_1 < p_2 < \dots < p_{k_i}$임이 보장됩니다.

출력

총 $q + 1$개의 줄을 출력하며, 각 줄에는 답을 나타내는 부동소수점 수를 출력합니다.

첫 번째 줄은 초기 배열에 대한 답이고, 이어지는 $q$개의 줄은 각 수정 그룹 이후의 답입니다.

정답과의 상대 오차 또는 절대 오차가 $10^{-9}$ 이하이면 정답으로 인정됩니다.

예제

입력 1

2
1 2
1 1
2
1
2 1 2
1
1 1 2

출력 1

1.333333333333
3.000000000000
4.000000000000

입력 2

6
1 1 4 5 1 4
2 3 3 3 3 3
0

출력 2

9.013888888889

참고

이 문제는 입력 크기가 크므로 빠른 입출력 방법을 사용하시기 바랍니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.