fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int MOD = 998244353;
  7.  
  8. int main(){
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(0);
  11.     int N;
  12.     cin >> N;
  13.     vector<int> C(2*N);
  14.     for(auto &x: C) cin >> x;
  15.     vector<int> R(N);
  16.     for(auto &x: R) cin >> x;
  17.     vector<int> B(N);
  18.     for(auto &x: B) cin >> x;
  19.  
  20.     // Create S = {1,...,2N} \ B
  21.     vector<bool> is_B(2*N +1, false);
  22.     for(int i=0;i<N;i++) is_B[B[i]] = true;
  23.     vector<int> S;
  24.     for(int x=1;x<=2*N;x++) if(!is_B[x]) S.push_back(x);
  25.     // Sort S
  26.     sort(S.begin(), S.end());
  27.  
  28.     // Map from B_i to i
  29.     vector<int> map_b(2*N +1, -1);
  30.     for(int i=0;i<N;i++) map_b[B[i]] = i;
  31.  
  32.     // Initialize x_fixed
  33.     vector<int> x_fixed(N, -1);
  34.     // Initialize used_S
  35.     vector<bool> used_S_flag(2*N +1, false);
  36.  
  37.     bool invalid = false;
  38.  
  39.     for(int p=0; p<2*N && !invalid; p++){
  40.         if(C[p] == -1) continue;
  41.         int v = C[p];
  42.         if(v >=1 && v <= 2*N && is_B[v]){
  43.             // v ∈ B
  44.             int i = map_b[v];
  45.             if(i == -1){
  46.                 invalid = true;
  47.                 break;
  48.             }
  49.             if(p == 2*i){
  50.                 // p == 2i+1 in 0-based index
  51.                 // A_{2i} = B_i
  52.                 // Thus, A_{2i-1} = x_i
  53.                 if(C[2*i -1] != -1){
  54.                     int x_i = C[2*i -1];
  55.                     // Check x_i ∈ S
  56.                     if(x_i <1 || x_i >2*N || is_B[x_i]){
  57.                         invalid = true;
  58.                         break;
  59.                     }
  60.                     // Check if x_i is already used
  61.                     if(used_S_flag[x_i]){
  62.                         invalid = true;
  63.                         break;
  64.                     }
  65.                     // Check R_i constraints
  66.                     if(R[i] ==0 && x_i <= B[i]){
  67.                         invalid = true;
  68.                         break;
  69.                     }
  70.                     if(R[i] ==1 && x_i >= B[i]){
  71.                         invalid = true;
  72.                         break;
  73.                     }
  74.                     x_fixed[i] = x_i;
  75.                     used_S_flag[x_i] = true;
  76.                 }
  77.             }
  78.             else{
  79.                 // p ==2i-1
  80.                 // A_{2i-1} = B_i
  81.                 // Thus, A_{2i} = x_i
  82.                 if(C[2*i] != -1){
  83.                     int x_i = C[2*i];
  84.                     // Check x_i ∈ S
  85.                     if(x_i <1 || x_i >2*N || is_B[x_i]){
  86.                         invalid = true;
  87.                         break;
  88.                     }
  89.                     // Check if x_i is already used
  90.                     if(used_S_flag[x_i]){
  91.                         invalid = true;
  92.                         break;
  93.                     }
  94.                     // Check R_i constraints
  95.                     if(R[i] ==0 && x_i <= B[i]){
  96.                         invalid = true;
  97.                         break;
  98.                     }
  99.                     if(R[i] ==1 && x_i >= B[i]){
  100.                         invalid = true;
  101.                         break;
  102.                     }
  103.                     x_fixed[i] = x_i;
  104.                     used_S_flag[x_i] = true;
  105.                 }
  106.             }
  107.         }
  108.         else if(v >=1 && v <= 2*N){
  109.             // v ∈ S
  110.             // Assign x_i = v to pair i
  111.             int i = (p /2);
  112.             if(i >= N){
  113.                 invalid = true;
  114.                 break;
  115.             }
  116.             if(p == 2*i){
  117.                 // A_{2i} = x_i = v
  118.                 if(R[i] ==0 && v <= B[i]){
  119.                     invalid = true;
  120.                     break;
  121.                 }
  122.                 if(R[i] ==1 && v >= B[i]){
  123.                     invalid = true;
  124.                     break;
  125.                 }
  126.                 if(used_S_flag[v]){
  127.                     invalid = true;
  128.                     break;
  129.                 }
  130.                 x_fixed[i] = v;
  131.                 used_S_flag[v] = true;
  132.             }
  133.             else{
  134.                 // p ==2i-1
  135.                 // A_{2i-1} = x_i = v
  136.                 if(R[i] ==0 && v <= B[i]){
  137.                     invalid = true;
  138.                     break;
  139.                 }
  140.                 if(R[i] ==1 && v >= B[i]){
  141.                     invalid = true;
  142.                     break;
  143.                 }
  144.                 if(used_S_flag[v]){
  145.                     invalid = true;
  146.                     break;
  147.                 }
  148.                 x_fixed[i] = v;
  149.                 used_S_flag[v] = true;
  150.             }
  151.         }
  152.         else{
  153.             // Invalid value
  154.             invalid = true;
  155.             break;
  156.         }
  157.     }
  158.  
  159.     if(invalid){
  160.         cout << "0";
  161.         return 0;
  162.     }
  163.  
  164.     // Collect group0 and group1 pairs
  165.     vector<int> group0_pairs;
  166.     vector<int> group1_pairs;
  167.     for(int i=0;i<N;i++){
  168.         if(R[i] ==0 && x_fixed[i] == -1){
  169.             group0_pairs.push_back(i);
  170.         }
  171.         if(R[i] ==1 && x_fixed[i] == -1){
  172.             group1_pairs.push_back(i);
  173.         }
  174.     }
  175.     int K = group0_pairs.size();
  176.     int L = group1_pairs.size();
  177.  
  178.     // Collect S_remaining
  179.     vector<int> S_remaining;
  180.     for(auto x: S){
  181.         if(!used_S_flag[x]){
  182.             S_remaining.push_back(x);
  183.         }
  184.     }
  185.  
  186.     // Assign group0
  187.     // Sort group0_pairs in decreasing B_j
  188.     sort(group0_pairs.begin(), group0_pairs.end(), [&](const int a, const int b)->bool{
  189.         return B[a] > B[b];
  190.     });
  191.     // Sort S_remaining in increasing order
  192.     sort(S_remaining.begin(), S_remaining.end());
  193.  
  194.     ll group0_assign =1;
  195.     for(int j=0; j<K; j++){
  196.         int b_j = B[group0_pairs[j]];
  197.         // Find number of S_remaining > b_j
  198.         // Using upper_bound
  199.         int cnt = S_remaining.end() - upper_bound(S_remaining.begin(), S_remaining.end(), b_j);
  200.         ll term = (ll)cnt - (K - j -1);
  201.         if(term <0){
  202.             invalid = true;
  203.             break;
  204.         }
  205.         group0_assign = (group0_assign * term) % MOD;
  206.     }
  207.     if(invalid){
  208.         cout << "0";
  209.         return 0;
  210.     }
  211.  
  212.     // Assign group1
  213.     // Sort group1_pairs in increasing B_j
  214.     sort(group1_pairs.begin(), group1_pairs.end(), [&](const int a, const int b)->bool{
  215.         return B[a] < B[b];
  216.     });
  217.     // S_remaining is still sorted in increasing order
  218.     ll group1_assign =1;
  219.     for(int j=0; j<L; j++){
  220.         int d_j = B[group1_pairs[j]];
  221.         // Find number of S_remaining < d_j
  222.         // Using lower_bound
  223.         int cnt = lower_bound(S_remaining.begin(), S_remaining.end(), d_j) - S_remaining.begin();
  224.         ll term = (ll)cnt - j;
  225.         if(term <0){
  226.             invalid = true;
  227.             break;
  228.         }
  229.         group1_assign = (group1_assign * term) % MOD;
  230.     }
  231.     if(invalid){
  232.         cout << "0";
  233.         return 0;
  234.     }
  235.  
  236.     ll assignments_count = (group0_assign * group1_assign) % MOD;
  237.  
  238.     // Now, compute arrangements_count
  239.     ll arrangements_count =1;
  240.     for(int i=0;i<N;i++){
  241.         if(C[2*i] != -1 && C[2*i+1] != -1){
  242.             // Both positions fixed
  243.             if( (C[2*i] == B[i] && C[2*i+1] == x_fixed[i]) || (C[2*i] == x_fixed[i] && C[2*i+1] == B[i]) ){
  244.                 // arrangements_count *=1
  245.                 continue;
  246.             }
  247.             else{
  248.                 invalid = true;
  249.                 break;
  250.             }
  251.         }
  252.         else if(C[2*i] != -1 || C[2*i+1] != -1){
  253.             bool ok = false;
  254.             if(C[2*i] != -1){
  255.                 if(C[2*i] == B[i] || C[2*i] == x_fixed[i]){
  256.                     ok = true;
  257.                 }
  258.             }
  259.             if(C[2*i+1] != -1){
  260.                 if(C[2*i+1] == B[i] || C[2*i+1] == x_fixed[i]){
  261.                     ok = true;
  262.                 }
  263.             }
  264.             if(ok){
  265.                 // arrangements_count *=1
  266.                 continue;
  267.             }
  268.             else{
  269.                 invalid = true;
  270.                 break;
  271.             }
  272.         }
  273.         else{
  274.             // Neither position fixed
  275.             arrangements_count = (arrangements_count * 2) % MOD;
  276.         }
  277.     }
  278.  
  279.     if(invalid){
  280.         cout << "0";
  281.         return 0;
  282.     }
  283.  
  284.     ll total = (assignments_count * arrangements_count) % MOD;
  285.     cout << total;
  286. }
  287.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
1
1 -1
0
2
stdout
copy 
Standard output is empty
https://ideone.com/mAqrj2
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!