2019杭电多校第五场

比赛记录

@byf水题写错一发，边界没考虑，变量还写错，一发罚时加很晚才过。1004忘记结构体重载运算符中的gcd也带一个log，TLE2发，而且这题花了太多时间。

@shl exkmp板子想不起来，先用后缀数组T了一发

@lfw 一上场用kmp写exkmp的题，结果发现不太对，有点冲动了，应该能推出样例再写的。1005一开始没想清楚，计数有问题，所以花了很久时间用对样例的调试来想清楚怎么计数。

题解

1001 fraction
题解：https://blog.csdn.net/baiyifeifei/article/details/98606715

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p,a;
//solve "pa/pb<x/y<=qa/qb" 's min(y),min(x)
void solve(LL pa,LL pb,LL qa,LL qb,LL &x,LL &y)
{
    LL z=(pa+pb-1)/pb;
    if(z<=qa/qb){
        x=z;y=1;
        return ;
    }
    pa-=(z-1)*pb;qa-=(z-1)*qb;
    solve(qb,qa,pb,pa,y,x);
    x+=(z-1)*y;
}
int main()
{
    int t;
    scanf("%d",&t);
    LL x,y;
    while(t--)
    {
        scanf("%lld%lld",&p,&a);
        solve(p,a,p,a-1,x,y);
        printf("%lld/%lld
",x*a-p*y,x);
    }
}

1002 three arrays

题解：https://blog.csdn.net/liufengwei1/article/details/98536161

#include<bits/stdc++.h>
#define maxl 100010
using namespace std;
 
int n,m,tota,totb,sum;
int ans[maxl],mi[30];
int a[maxl],b[maxl];
int suma[maxl*31],sumb[maxl*31];
int tra[maxl*31][2],trb[maxl*31][2];
int q[maxl],w[maxl];
vector <int> numa[maxl*31],numb[maxl*31];
vector <int> :: iterator it;
bool ina[maxl],inb[maxl];
 
inline void inserta(int id,int x)
{
    int u=0,c;
    for(int i=29;i>=0;i--)
    {
        suma[u]++;
        c=(x>>i)&1;
        if(!tra[u][c])
            tra[u][c]=++tota;
        u=tra[u][c];
    }
    suma[u]++;numa[u].push_back(id);
}
 
inline void insertb(int id,int x)
{
    int u=0,c;
    for(int i=29;i>=0;i--)
    {
        sumb[u]++;
        c=(x>>i)&1;
        if(!trb[u][c])
            trb[u][c]=++totb;
        u=trb[u][c];
    }
    sumb[u]++;numb[u].push_back(id);
}
 
inline void prework()
{
    for(int i=0;i<=tota;i++)
    {
        tra[i][0]=tra[i][1]=0;
        suma[i]=0;numa[i].clear();    
    }
    for(int i=0;i<=totb;i++)
    {
        trb[i][0]=trb[i][1]=0;
        sumb[i]=0,numb[i].clear();
    }
    scanf("%d",&n);
    tota=0;totb=0;
    for(int i=1;i<=n;i++)
    {    
        scanf("%d",&a[i]);
        inserta(i,a[i]);ina[i]=true;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        insertb(i,b[i]);inb[i]=true;
    }
}
 
inline int finda(int x)
{
    int u=0,c,tmp=0;
    for(int i=29;i>=0;i--)
    {
        c=(x>>i)&1;
        if(!tra[u][c])
            u=tra[u][c^1];
        else 
            u=tra[u][c];
    }
    it=numa[u].end();--it;
    return (*it);
}
 
inline int findb(int x)
{
    int u=0,c;
    for(int i=29;i>=0;i--)
    {
        c=(x>>i)&1;
        if(!trb[u][c])
            u=trb[u][c^1];
        else
            u=trb[u][c];
    }
    it=numb[u].end();--it;
    return (*it);
}
 
inline void dela(int x)
{
    int u=0,c,last;suma[u]--;
    for(int i=29;i>=0;i--)
    {
        c=(x>>i)&1;last=u;
        u=tra[u][c];
        suma[u]--;
        if(suma[u]==0)
            tra[last][c]=0;
    }
    it=numa[u].end();--it;
    numa[u].erase(it);
}
 
inline void delb(int x)
{
    int u=0,c,last;sumb[u]--;
    for(int i=29;i>=0;i--)
    {
        c=(x>>i)&1;last=u;
        u=trb[u][c];
        sumb[u]--;
        if(sumb[u]==0)
            trb[last][c]=0; 
    }
    it=numb[u].end();--it;
    numb[u].erase(it);
}
 
inline void dfs(int k)
{
    int id;
    if(k&1)
    {
        id=finda(b[q[k-1]]);
        if(id==q[k-2] && k-2>0)
        {
            delb(b[q[k-1]]);
            dela(a[id]);
            inb[q[k-1]]=false;
            ina[id]=false;
            ans[++ans[0]]=b[q[k-1]]^a[id];
            k-=2;sum--;
        }
        else
        {
            w[k]=b[q[k-1]]^a[id];
            q[k]=id;k++;
        }
        if(sum>0)
            dfs(k);
    }
    else
    {
        id=findb(a[q[k-1]]);
        if(id==q[k-2] && k-2>0)
        {
            dela(a[q[k-1]]);
            delb(b[id]);
            ina[q[k-1]]=false;
            inb[id]=false;
            ans[++ans[0]]=a[q[k-1]]^b[id];
            k-=2;sum--;
        }
        else
        {
            w[k]=a[q[k-1]]^b[id];
            q[k]=id;k++;
        }
        if(sum>0)
            dfs(k);
    }
}
 
inline void mainwork()
{
    ans[0]=0;sum=n;
    for(int i=1;i<=n;i++)
    if(ina[i])
    {
        q[1]=i;
        dfs(2);
    }
}
 
inline void print()
{
    sort(ans+1,ans+1+ans[0]);
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i],(i==n)?'
':' ');
}
 
int main()
{
    mi[0]=1;
    for(int i=1;i<=29;i++)
        mi[i]=mi[i-1]*2;
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}

1003 geometric problem

unsolved

1004 equation

#include<bits/stdc++.h>
using namespace std;

namespace IO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 

    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='
'||ch=='
'||ch=='	';} 
    inline bool read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror) return false; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; return true;
    } 
    inline bool read(ll &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror) return false; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; return true;
    } 
    inline bool read(double &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror) return false; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (ch=='.'){ 
            double tmp=1; ch=nc(); 
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); 
        } 
        if (sign)x=-x; return true;
    } 
    inline bool read(char *s){ 
        char ch=nc(); 
        for (;blank(ch);ch=nc()); 
        if (IOerror) return false; 
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; 
        *s=0; return true;
    } 
    inline void read(char &c){ 
        for (c=nc();blank(c);c=nc()); 
        if (IOerror){c=-1;return;} 
    } 
    //fwrite->write 
    struct Ostream_fwrite{ 
        char *buf,*p1,*pend; 
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} 
        void out(char ch){ 
            if (p1==pend){ 
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf; 
            } 
            *p1++=ch; 
        } 
        void print(int x){ 
            static char s[15],*s1;s1=s; 
            if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
            while(x)*s1++=x%10+'0',x/=10; 
            while(s1--!=s)out(*s1); 
        } 
        void println(int x){ 
            static char s[15],*s1;s1=s; 
            if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
            while(x)*s1++=x%10+'0',x/=10; 
            while(s1--!=s)out(*s1); out('
'); 
        } 
        void print(ll x){ 
            static char s[25],*s1;s1=s; 
            if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
            while(x)*s1++=x%10+'0',x/=10; 
            while(s1--!=s)out(*s1); 
        } 
        void println(ll x){ 
            static char s[25],*s1;s1=s; 
            if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
            while(x)*s1++=x%10+'0',x/=10; 
            while(s1--!=s)out(*s1); out('
'); 
        } 
        void print(double x,int y){ 
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000, 
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL, 
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL}; 
            if (x<-1e-12)out('-'),x=-x;x*=mul[y]; 
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1; 
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2); 
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i) {}; print(x3);} 
        } 
        void println(double x,int y){print(x,y);out('
');} 
        void print(char *s){while (*s)out(*s++);} 
        void println(char *s){while (*s)out(*s++);out('
');} 
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} 
        ~Ostream_fwrite(){flush();} 
    }Ostream; 
    inline void print(int x){Ostream.print(x);} 
    inline void println(int x){Ostream.println(x);} 
    inline void print(char x){Ostream.out(x);} 
    inline void println(char x){Ostream.out(x);Ostream.out('
');} 
    inline void print(ll x){Ostream.print(x);} 
    inline void println(ll x){Ostream.println(x);} 
    inline void print(double x,int y){Ostream.print(x,y);} 
    inline void println(double x,int y){Ostream.println(x,y);} 
    inline void print(char *s){Ostream.print(s);} 
    inline void println(char *s){Ostream.println(s);} 
    inline void println(){Ostream.out('
');} 
    inline void flush(){Ostream.flush();}
    #undef ll 
    #undef OUT_SIZE 
    #undef BUF_SIZE 
};
using namespace IO;


typedef long long LL;
const int size=1e5+5;
int suma[size],sumb[size];
struct frac{
    int son,mon;
    frac(){}
    frac(int _son,int _mon)
    {
        if(_son==0) {son=0,mon=1;}
        else {
            int g=__gcd(_son,_mon);
            son=_son/g;
            mon=_mon/g;
            if(son>0&&mon<0)son=-son,mon=-mon;
        }
    }
    friend bool operator<(frac x,frac y)
    {
        return 1LL*y.mon*x.son<1LL*x.mon*y.son;
    }
    friend bool operator==(frac x,frac y)
    {
        if((x.son==y.son)&&(x.mon==y.mon)) return true;;
        return false;
    }
    friend bool operator<=(frac x,frac y)
    {
        if(x<y) return true;
        if((x.son==y.son)&&(x.mon==y.mon)) return true;
        return false;
    }
};
struct line{
    int a,b;
    frac p;
    line(){}
    line(int a,int b):a(a),b(b),p(-b,a){}
    friend bool operator<(line x,line y)
    {
        return x.p<y.p;
    }
}L[size];
vector<frac> ans;
int main()
{
    int t;
    //scanf("%d",&t);
    read(t); 
    int n,c;
    while(t--)
    {
        //scanf("%d%d",&n,&c);
        read(n);read(c);
        suma[0]=sumb[0]=0;
        bool flag;
        int a,b;
        for(int i=1;i<=n;i++)
        {
            //scanf("%d%d",&a,&b);
            read(a);read(b);
            L[i]=line(a,b);
        }
        sort(L+1,L+1+n);
        ans.clear();
        for(int i=1;i<=n;i++)
        {
            suma[i]=suma[i-1]+L[i].a;
            sumb[i]=sumb[i-1]+L[i].b;
        }
        int newa=-suma[n],newb=-sumb[n];
        frac tp;
        if(newa==0)
        {
            if(newb==c)
            {
                println(-1);
                //puts("-1");
                continue;
            }
        }
        if(newa!=0){
            tp=frac(c-newb,newa);
            if(tp<=L[1].p) ans.push_back(tp);
        }
        flag=true;
        for(int i=1;i<n;i++)
        {
            newa=2*suma[i]-suma[n];
            newb=2*sumb[i]-sumb[n];
            if(newa==0)
            {
                if(newb==c)
                {
                    println(-1);
                    //puts("-1");
                    flag=false;
                    break;
                }
                else continue;
            }
            tp=frac(c-newb,newa);
            if(tp<=L[i+1].p&&L[i].p<=tp) ans.push_back(tp);
        }
        if(!flag) continue;
        newa=suma[n],newb=sumb[n];
        if(newa==0)
        {
            if(newb==c)
            {
                println(-1);
                //puts("-1");
                continue;
            }
        }
        if(newa!=0){
            tp=frac(c-newb,newa);
            if(L[n].p<=tp) ans.push_back(tp);
        }
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        int len=ans.size();
        //printf("%d",len);
        print(len);
        for(int i=0;i<len;i++)
        {
            print(' ');
            print(ans[i].son);
            print('/');
            print(ans[i].mon);
            //printf(" %d/%d",ans[i].son,ans[i].mon);
        }
        print('
');
        //puts("");
    }
    return 0;
}

1005 permutation 1

题解：https://blog.csdn.net/liufengwei1/article/details/98515203

#include<bits/stdc++.h>
#define maxl 45
using namespace std; 
 
int n;
long long k;
int p[maxl];
int ans[maxl];
long long jc[maxl];
int ok[maxl*2];
struct node
{
    int a[maxl];
    int in[maxl];
    void init()
    {
        for(int i=0;i<=20;i++)
            a[i]=0,in[i]=false;
    }
};
vector <node> tmp;
vector <node> :: iterator it;
 
inline void prework()
{
    scanf("%d%lld",&n,&k);
}
 
inline void solve(int u)
{
    for(int i=1-n;i<=n-1;i++)
        ok[i+n]=0;
    bool flag;node d;
    d.init();
    if(u==1)
    {
        tmp.clear();
        if(p[u]<0)
        {
            for(int i=n;i>=1-p[u];i--)
            {
                d.a[1]=i;d.a[2]=i+p[u];
                d.in[i]=true;d.in[i+p[u]]=true;
                for(int j=1;j<=n;j++)
                if(!d.in[j])
                    ok[j-d.a[2]+n]++;
                tmp.push_back(d);
                d.in[i]=false;d.in[i+p[u]]=false;
            }
        }
        else
        {
            for(int i=1;i<=n-p[u];i++)
            {
                d.a[1]=i;d.a[2]=i+p[u];
                d.in[i]=true;d.in[i+p[u]]=true;
                for(int j=1;j<=n;j++)
                if(!d.in[j])
                    ok[j-d.a[2]+n]++;
                tmp.push_back(d);
                d.in[i]=false;d.in[i+p[u]]=false;
            }
        }
    }
    else
    {
        int x;
        for(it=tmp.begin();it!=tmp.end();)
        {
            x=it->a[u]+p[u];
            if(x<=n && x>0)
            {    if( !(it->in[x]))
                {
                    it->a[u+1]=x;
                    it->in[x]=true;
                    for(int j=1;j<=n;j++)
                    if(!(it->in[j]))
                        ok[j-x+n]++;
                    ++it;
                }
                else
                    tmp.erase(it);
            }
            else
                tmp.erase(it);
        }
    }
}
 
inline int abs(int x)
{
    if(x<0) return -x;
    else return x;
}
 
inline void dfs(int u,long long res)
{
    long long t;
    int sum;
    for(int i=1-n;i<=n-1;i++)
    if(ok[i+n])
    {
        sum=ok[i+n];
        if(k<=sum*jc[n-1-u])
        {
            p[u]=i;
            solve(u);
            if(u<n-1)
                dfs(u+1,k);    
            return;
        }
        k-=sum*jc[n-1-u];
    }
}
 
inline void mainwork()
{
    for(int i=1-n;i<=n-1;i++)
        ok[i+n]=n-abs(i);
    ok[0+n]=0;
    tmp.clear();
    dfs(1,k);
}
 
inline void print()
{
    it=tmp.begin();
    for(int i=1;i<=n;i++)
        printf("%d%c",it->a[i],(i==n)?'
':' ');
}
 
int main()
{
    jc[0]=1;jc[1]=1;
    for(int i=1;i<=20;i++)
        jc[i]=jc[i-1]*i;
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}

1006 string matching

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5; 
char ss[maxn];
ll Next[maxn], extend[maxn];
#define fi first
#define se second
#define INF 0x3f3f3f3f

//预处理计算Next数组
void getNext(char str[])
{
    int i = 0, j, po, len = strlen(str);
    Next[0] = len; //初始化next[0]
    while (str[i] == str[i + 1] && i + 1 < len)
        i++;
    Next[1] = i; //计算next[1]
    po = 1; //初始化po的位置
    for (i = 2; i < len; i++) {
        if (Next[i - po] + i < Next[po] + po) //第一种情况，可以直接得到next[i]的值
            Next[i] = Next[i - po];
        else //第二种情况，要继续匹配才能得到next[i]的值
        {
            j = Next[po] + po - i;
            if (j < 0)
                j = 0; //如果i>po+Next[po],则要从头开始匹配
            while (i + j < len && str[j] == str[j + i])
                j++;
            Next[i] = j;
            po = i; //更新po的位置
        }
    }
}

//计算extend数组
void EXKMP(char s1[], char s2[])
{
    int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
    getNext(s2); 
    while (s1[i] == s2[i] && i < l2 && i < len)
        i++;
    extend[0] = i;
    po = 0; 
    for (i = 1; i < len; i++) {
        if (Next[i - po] + i < extend[po] + po) 
            extend[i] = Next[i - po];
        else 
        {
            j = extend[po] + po - i;
            if (j < 0)
                j = 0; 
            while (i + j < len && j < l2 && s1[j + i] == s2[j])
                j++;
            extend[i] = j;
            po = i; 
        }
    }
}

int t;
int main()
{
    scanf("%d", &t);
    while (t--) 
    {
        scanf("%s", ss);
        EXKMP(ss, ss);
        int len = strlen(ss);
        ll ans = 0;
        for(int i=1;i<len;++i)
        {
            if(extend[i] + i == len)
                ans += extend[i];
            else
                ans += extend[i] + 1;
        }
        printf("%lld
", ans);
    }
    return 0;
}

1007 permutation 2

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int size=1e5+5;
int dp[size];
void init()
{
    dp[0]=1;dp[1]=1;dp[2]=1;dp[3]=2;
    for(int i=4;i<size;i++)
    {
        dp[i]=(dp[i-1]+dp[i-3])%mod;
    }
}
int main()
{
    int t;
    int n,x,y;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&y);
        int beg,ed;
        if(x==1) beg=1;else beg=x+1;
        if(y==n) ed=n;else ed=y-1;
        if(ed-beg<0)
        {
            puts("0");
            continue;
        }
        printf("%d
",dp[ed-beg]);
    }
}

1008 line symmetric

题解：https://blog.csdn.net/liufengwei1/article/details/98664030

#include<bits/stdc++.h>
#define maxl 1010
#define eps 1e-9
using namespace std;
 
inline int sgn(double x)
{
    if(x>-eps && x<eps) return 0;
    if(x<0) return -1;
    else    return 1;
}
 
struct point
{
    double x,y;
    point(double a=0,double b=0)
    {
        x=a,y=b;
    }
    point operator - (const point &b)const
    {
        return point(x-b.x,y-b.y);
    }
    point operator + (const point &b)const
    {
        return point(x+b.x,y+b.y);
    }
    friend point operator / (point p,double t)
    {
        return point(p.x/t,p.y/t);
    }
};
inline double dot(point a,point b)
{
    return a.x*b.x+a.y*b.y;
}
inline double det(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
struct line
{
    point s,e;double k;
    line(point a=point(),point b=point())
    {
        s=a,e=b;
        k=atan2(e.y-s.y,e.x-s.x);
    }
    bool operator < (const line &b)const
    {
        return k<b.k;
    }
};
 
int n;
point a[maxl]; 
line b[maxl];
bool ans,flag;
 
inline void prework()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
}
 
inline void mainwork()
{
    if(n<=4)
    {
        ans=true;
        return;
    }
    /*if(n==6 && a[1].x==0 && a[1].y==12)
    {
        ans=false;
        return;
    }*/
    ans=false;point mid,midd;
    int s,t,ss,tt,cnt,lasts,lastt;
    bool lastflag; 
    for(int i=1;i<=n;i++)
    {
        s=i-1;t=i+1;
        if(s<1) s=n;
        if(t>n) t=1;
        mid=a[s]+a[t];mid=mid/2;
        ss=s;tt=t;cnt=0;lastflag=false;
        if(sgn(dot(a[i]-mid,a[t]-a[s]))!=0)
            cnt=1;
        for(int j=1;j<=n/2-1;j++)
        {         
             
            lasts=ss;lastt=tt;
            ss--;tt--;
            if(ss<1) ss=n;
            if(tt>n) tt=1;
            midd=a[ss]+a[tt];midd=midd/2;
            if(lastflag)
            {
                if(sgn(dot(a[ss]-mid,a[s]-mid))<=0 && 
                   sgn(dot(a[lasts]-mid,a[s]-mid))<=0)
                {
                    cnt++;
                    break;
                }
                if(sgn(dot(a[tt]-mid,a[t]-mid))<=0 && 
                   sgn(dot(a[lastt]-mid,a[t]-mid))<=0)
                {
                    cnt++;
                    break;
                }
            }
            lastflag=false;  
            if(sgn(dot(a[t]-a[s],mid-midd))!=0 ||
               sgn(dot(a[tt]-a[ss],mid-midd))!=0)
                   cnt++,lastflag=true; 
 
            if(sgn(dot(a[ss]-mid,a[lasts]-mid))<=0 &&
               sgn(dot(a[tt]-mid,a[lastt]-mid))<=0)
                   cnt++,lastflag=true;
        }
        if(cnt<=1)
        {
            ans=true;
            return;
        }
    }
    for(int i=1;i<=n && !ans;i++)
    {
        s=i;t=i+1;
        if(s<1) s=n;
        if(t>n) t=1;
        ss=s;tt=t;lastflag=false;
        mid=a[s]+a[t];mid=mid/2;cnt=0;
        for(int j=1;j<=(n-1)/2;j++)
        {      
               
            lasts=ss;lastt=tt;      
            ss--;tt++;
            if(ss<1) ss=n;
            if(tt>n) tt=1;
            if(lastflag)
            {
                if(sgn(dot(a[ss]-mid,a[s]-mid))<=0 && 
                   sgn(dot(a[lasts]-mid,a[s]-mid))<=0)
                {
                    cnt++;
                    break;
                }
                if(sgn(dot(a[tt]-mid,a[t]-mid))<=0 && 
                   sgn(dot(a[lastt]-mid,a[t]-mid))<=0)
                {
                    cnt++;
                    break;
                }
            }
            lastflag=false;
            midd=a[ss]+a[tt];midd=midd/2;
            if(sgn(dot(a[t]-a[s],mid-midd))!=0 ||
               sgn(dot(a[tt]-a[ss],mid-midd))!=0)
                   cnt++,lastflag=true; 
 
            if(sgn(dot(a[ss]-mid,a[lasts]-mid))<=0 &&
               sgn(dot(a[tt]-mid,a[lastt]-mid))<=0)
                   cnt++,lastflag=true;
        }
          if(cnt<=1)
          {
            ans=true;
            return;
        }
    }
}
 
inline void print()
{
    if(ans)
        puts("Y");
    else
        puts("N"); 
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}

1009 discrete logarithm problem

unsolved

1010 find hidden array

unsolved