TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Description

Original Description

NPSC 國是個團結的國家。「轉」作為該國的古老文化之一,幾乎所有 NPSC 國的程式競賽選手,在寫到平衡二元樹(balanced binary tree)相關的題目時都會寫伸展樹(splay tree)。然而,總會有一些意圖破壞國家和諧的分離主義者,他們總是寫「分裂/合併式樹堆」(merge-split treap),意圖分裂族群。為了維護二元樹的主權與領土完整,NPSC 國通過了《反分裂二元樹法》,以追蹤並調查這些傷害民族感情的人們。

NPSC 國的執法人員總共調查了 $N$ 個分離主義者,將他們編號為 $0$ 到 $N-1$,並且發現任兩個分離主義者之間都有直接聯繫。某一天,NPSC 國的情報單位發現了一些奇怪的現象,可以描述為很多個事件,每個事件都是這 $N$ 個人中的某 $K$ 個人不再與另外 $N-K$ 個人直接聯繫。調查人員認為這可能代表著分離主義者之間發生了內鬨,而開始分門結黨、彼此分離。這件事對國家的發展有重要影響,因此調查人員把每一個這樣的事件全部記錄在一份機密文件上。

你身為 CSPN 國的間諜,輾轉取得了這份文件。這份文件經過加密,但是你成功攔截到了解密這份文件的公式,因此你決定把它解密來研究,以備不時之需。

具體來說,要解密這份文件需要一個解密函數,定義為 $F(x)=(x\ \text{xor}\ A) \bmod N$,其中 $A$ 的初始值是給定的,但會隨著解密的過程改變。($x\ \text{xor}\ A$ 代表 $x$ 和 $A$ 的「按位異或」(exclusive or),即 C / C++ 中的 $x$ ^ $A$ ; $p\bmod N$ 代表 $p$ 除以 $N$ 的餘數,即 C / C++ 中的$p\% N$ 。

這份文件解密前可以分為 $M$ 行,每行有許多個介於 $0$ 到 $2^ {32}-1$ 之間的非負整數,且都是下列兩種格式之一:

  1. $1\ Q\ a_1\ a_2\ a_3 \cdots a_Q$: 代表編號為 $F(a_1),F(a_2),F(a_3),\cdots,F(a_Q)$ 的人們不再與其他 $N-Q$ 個人直接聯繫。若這群人的集合為 $T$,而所有人的集合為 $S$,在 $T$ 中的任兩人的聯繫狀態並不會改變,在 $S\setminus T$ 之間的任兩人亦同。一個人有可能在這個清單中出現兩次以上,但是與只出現一次是同樣的意思。保證$1\leq Q\leq N$。
  2. $2\ a\ b$: 根據編號 $F(a),F(b)$ 的人當前是否有直接聯繫改變函數 $A$ 的值:若這兩人當前有直接聯繫,則將 $A$ 改變為 $(22695477A+1) \bmod 2^ {32}$;否則,將 $A$ 改變為 $(69069A+1) \bmod 2^ {32}$。假如 $F(a)=F(b)$,則視為兩人有直接聯繫。

這份文件是按照事件的發生順序排序,而一開始任兩個人都有直接聯繫。解密也必須按照文件的順序,也就是說遇到第二種格式時只依照所有該行之前的事件作判斷。

然而,因為這份文件實在是過於龐大,所以你決定寫一個程式來幫你解密這份文件。又因為把整份解密文件全部存下來比較費時,所以你決定先存下解密結束時的 $A$ 值就好了。

Original Input Format

輸入的第一行有三個非負整數 $N,M,A$,分別代表總人數、機密文件的行數與解密時初始的 $A$ 值。
接下來有 $M$ 行,代表要解密的文件。詳細的格式請見題目敘述。

  • $2\leq N\leq 3\times 10^ 6$
  • $1 \le M \le 5 \times 10^ 6$
  • $A$ 與所有文件中的數字均是介於 $0$ 和 $2^ {32}-1$ 之間的整數
  • $1 \le Q \le N$
  • 整份要被解密的文件最多只會有 $5\times 10^ 6$ 個數字。

Original Output Format

請輸出一行包含一個非負整數,代表整份文件解密結束之後的 $A$ 值。

Original Sample Input

Sample Input 1:
3 2 1
1 1 7
2 0 2

Sample Input 2:
3 2 1
1 1 7
2 0 3

Original Sample Output

Sample Output 1:
69070

Sample Output 2:
22695478

Original Limits

  • Time Limit: 6 second
  • Memory Limit: 1024 MB

Program To Be Hacked

#include <cstdio>
#include <cstdint>

const int kN = 3000007;
uint32_t now[kN];
int vis[kN];
inline bool Query(int a, int b) { return now[a] == now[b]; }

int main() {
  srand(time(NULL));
  int N, M;
  uint32_t A;
  scanf("%d%d%u", &N, &M, &A);
  auto F = [&](uint32_t x){ return (A ^ x) % N; };
  uint32_t val = 213;
  while (M--) {
    int type, Q;
    uint32_t a, b;
    scanf("%d", &type);
    if (type == 2) {
      scanf("%u%u", &a, &b);
      A = (Query(F(a), F(b)) ? 22695477 : 69069) * A + 1;
    } else {
      scanf("%d", &Q);
      val = rand();

      while (Q--) {
        scanf("%u", &a); a = F(a);
        if (vis[a] == M) continue;
        vis[a] = M; now[a] ^= val;
      }
    }
  }
  printf("%u\n", A);
}

Judge Method

請輸出一筆測試資料,使得上述的程式碼會輸出錯的答案。

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("3 2 1\n1 1 7\n2 0 2\n2 0 0\n");
}

Hint

你上傳的 code 當中,不能出現 clock 以及 time 這兩個子字串喔!

Input Format

Output Format

Sample Input

Sample Output

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1