Intelligence test(test)問題解

タイトルの説明

覇中知能テスト機構の一つの仕事は、一定の規則に従ってシーケンスの数字を削除し、確定した数列を得ることだ.
Lyxは覇中知能テスト機関の主管になることを渇望しているが、彼はこの仕事でよくやっていない.
彼はたくさんの練習をするつもりなので、彼の答えが正しいかどうかを迅速に判断するためのプログラムを書いてほしいと思っています.

入力

第1の動作の整数m(1<=m<=1000000)
2行目は、スペースで区切られたm個の整数ai(1<=ai<=1000000)を含み、最初のシーケンスを構成する.
第3の動作は、n個のLyxが一連の削除を経て得られるシーケンスを示す整数n(1<=n<=1000000)である.

            ， L（1<=L<=m）， L bi（1<=bi<=1000000）。

しゅつりょく

共n行、Lyxのシーケンスが確かに最初のシーケンスからいくつか削除された数で得られた場合、TAKが出力され、そうでなければNIEが出力される.

サンプル入力

7 1 5 4 5 7 8 6 4 5 1 5 5 8 6 3 2 2 2 3 5 7 8 4 1 5 7 4

サンプル出力

TAK NIE TAK NIE

の意見を打診

元のシーケンスからいくつかの数を削除することは、元のシーケンスのいくつかの数を保存する相対位置

に等しい.

アルゴリズム#アルゴリズム#

iはf[i][j]でiという数がj回目に現れるのはどこで

であるかを示す.

は、f配列

を1つのvectorで格納する.

残りは二分

です

コード#コード#

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#define MAXN 1000005
using namespace std;
int n,x,m,len,b[MAXN],farest;
bool flag;
vector<int >q[MAXN];
inline int wbs(int x,int v)
{
    int l=0,r=q[x].size()-1,mid,pos=n+1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(q[x][mid]>v)pos=q[x][mid],r=mid-1;
        else l=mid+1;
    }
    return pos;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        q[x].push_back(i);
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        farest=0;
        flag=true;
        scanf("%d",&len);
        for (int j=1;j<=len;j++)
            scanf("%d",&b[j]);
        for (int j=1;j<=len;j++)
        {
            farest=wbs(b[j],farest);
            if(farest>n){flag=false;break;}
        }
        if(flag==true)printf("TAK
");
        else printf("NIE
");
    }
    return 0;
}