题解 | #False coin#

#include <iostream>
using namespace std;

int all_in(int x,int left[1000][1000],int right[1000][1000],int n)
{
    int flag_l=1;
    for(int i=1;i<=n;i++)
    {
        if(left[i][x]!=1)
        {
            flag_l=0;
            break;
        }
    }
    int flag_r=1;
    for(int i=1;i<=n;i++)
    {
        if(right[i][x]!=1)
        {
            flag_r=0;
            break;
        }
    }
    return flag_l||flag_r;
}
int main() {
    int n, k;
    cin>>n>>k;
    int *a=new int[n+1]{0};
    int tmp_left[1000][1000]={0};
    int tmp_right[1000][1000]={0};
    int sum_equal=0;
    for(int i=0;i<k;i++)
    {
        int c;
        cin>>c;


        int *lst=new int[2*c];
        for(int j=0;j<2*c;j++)cin>>lst[j];
        char mark;
        cin>>mark;
        if(mark=='=')
        {
            for(int j=0;j<2*c;j++)a[lst[j]]=1;
        }
        else
        {
            sum_equal++;
            for(int f=0;f<=n;f++)
            {
                int flag=1;
                for(int j=0;j<2*c;j++)
                    if(f==lst[j])flag=0;
                if(flag==1)
                {
                    a[f]=flag;
                }
            }
            if(mark=='>')
            {
                for(int j=0;j<c;j++)tmp_left[sum_equal][lst[j]]=1;
                for(int j=c;j<2*c;j++)tmp_right[sum_equal][lst[j]]=1;
            }
            else
            {
                for(int j=0;j<c;j++)tmp_right[sum_equal][lst[j]]=1;
                for(int j=c;j<2*c;j++)tmp_left[sum_equal][lst[j]]=1;
            }

        }
    }
    a[0]=1;
    int t=0;
    for(int i=0;i<=n;i++)
    {
        //cout<<a[i]<<endl;
        if(a[i]==0)
        {
            if(t==0)t=i;
            else
            {
                t=0;
                //break;
            }
        }
    }
    //cout<<t;
    t=0;
    for(int i=0;i<=n;i++)
    {
        if(a[i]==0)
        {
            if(t==0)t=i;
            else
            {
                t=0;
                break;
            }
        }
    }
    if(t!=0)cout<<t;
    else
    {
        for(int i=0;i<=n;i++)
        {
            if(a[i]==0)
            {
                int g=all_in(i,tmp_left,tmp_right,sum_equal);
                if(g==0)a[i]=1;
            }
        }
        t=0;
        for(int i=0;i<=n;i++)
        {
            if(a[i]==0)
            {
                if(t==0)t=i;
                else
                {
                    t=0;
                    break;
                }
            }
        }
        cout<<t;
    }

}
// 64 位输出请用 printf("%lld")