QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#58636 | #4422. Two Permutations | qinjianbin# | TL | 0ms | 0kb | C++17 | 871b | 2022-10-27 10:27:59 | 2022-10-27 10:28:02 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int a[N], b[N], c[N], n;
unordered_map<ll, int> dp;
ll id(int i, int j)
{
return 1LL * i * 1e6 + j;
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
dp.clear();
scanf("%d", &n);
_for(i, 1, n)
{
int x; scanf("%d", &x);
a[x] = i;
}
_for(i, 1, n)
{
int x; scanf("%d", &x);
b[x] = i;
}
_for(i, 1, 2 * n) scanf("%d", &c[i]);
dp[id(0, 0)] = 1;
_for(k, 1, 2 * n)
{
int i = a[c[k]];
int j = k - i;
if(j >= 0) dp[id(i, j)] += dp[id(i - 1, j)];
j = b[c[k]];
i = k - j;
if(i >= 0) dp[id(i, j)] += dp[id(i, j - 1)];
}
printf("%d\n", dp[id(n, n)]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
282 1000 434 697 735 906 614 835 227 800 116 98 776 601 110 371 262 452 608 368 719 717 241 572 203 410 440 749 604 457 516 637 488 691 841 493 418 307 745 499 833 789 819 179 357 288 129 954 29 391 80 389 771 613 653 747 928 570 518 1000 547 587 727 778 669 554 426 899 256 681 515 532 409 677 533 3...