求帮优化时间复杂度
  • 板块学术版
  • 楼主wwkwwkwwk
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/9/3 22:04
  • 上次更新2023/10/27 12:39:01
查看原帖
求帮优化时间复杂度
743854
wwkwwkwwk楼主2022/9/3 22:04
    #pragma GCC diagnostic error "-std=c++11"
    #pragma GCC target("avx")
    #pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("inline")
    #pragma GCC optimize("-fgcse")
    #pragma GCC optimize("-fgcse-lm")
    #pragma GCC optimize("-fipa-sra")
    #pragma GCC optimize("-ftree-pre")
    #pragma GCC optimize("-ftree-vrp")
    #pragma GCC optimize("-fpeephole2")
    #pragma GCC optimize("-ffast-math")
    #pragma GCC optimize("-fsched-spec")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("-falign-jumps")
    #pragma GCC optimize("-falign-loops")
    #pragma GCC optimize("-falign-labels")
    #pragma GCC optimize("-fdevirtualize")
    #pragma GCC optimize("-fcaller-saves")
    #pragma GCC optimize("-fcrossjumping")
    #pragma GCC optimize("-fthread-jumps")
    #pragma GCC optimize("-funroll-loops")
    #pragma GCC optimize("-fwhole-program")
    #pragma GCC optimize("-freorder-blocks")
    #pragma GCC optimize("-fschedule-insns")
    #pragma GCC optimize("inline-functions")
    #pragma GCC optimize("-ftree-tail-merge")
    #pragma GCC optimize("-fschedule-insns2")
    #pragma GCC optimize("-fstrict-aliasing")
    #pragma GCC optimize("-fstrict-overflow")
    #pragma GCC optimize("-falign-functions")
    #pragma GCC optimize("-fcse-skip-blocks")
    #pragma GCC optimize("-fcse-follow-jumps")
    #pragma GCC optimize("-fsched-interblock")
    #pragma GCC optimize("-fpartial-inlining")
    #pragma GCC optimize("no-stack-protector")
    #pragma GCC optimize("-freorder-functions")
    #pragma GCC optimize("-findirect-inlining")
    #pragma GCC optimize("-fhoist-adjacent-loads")
    #pragma GCC optimize("-frerun-cse-after-loop")
    #pragma GCC optimize("inline-small-functions")
    #pragma GCC optimize("-finline-small-functions")
    #pragma GCC optimize("-ftree-switch-conversion")
    #pragma GCC optimize("-foptimize-sibling-calls")
    #pragma GCC optimize("-fexpensive-optimizations")
    #pragma GCC optimize("-funsafe-loop-optimizations")
    #pragma GCC optimize("inline-functions-called-once")
    #pragma GCC optimize("-fdelete-null-pointer-checks")
    #include<bits/stdc++.h>
    using namespace std;
    inline int read()
    {
    	long long x=0,f=1;char ch=getchar();
    	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    	return x*f;
    }
    struct node{
        int x,y,t;
    }a[10010],t[10010];
    int n;
    bool cmp(node X,node Y){
        return X.t<Y.t;
    }
    void qsort(int l,int r){
    	if(l==r) return;
    	long long m=(l+r)>>1;
    	qsort(l,m);
    	qsort(m+1,r);
    	int i=l,j=m+1,k=l;
    	while(i<=m&&j<=r){
    		if(cmp(a[i],a[j])) t[k++]=a[i++];
    		else t[k++]=a[j++];
    	}
    	while(i<=m) t[k++]=a[i++];
    	while(j<=r) t[k++]=a[j++];
    	for(i=l;i<=r;i++) a[i]=t[i];
    }
    int main(){
        n=read();
        for(int i=1;i<=n;i++){
    		a[i].t=read();
    		a[i].x=read();
    		a[i].y=read();
    	}
        qsort(1,n);
        int x=0,y=0,t=0;
        for(int i=1;i<=n;i++){
            if(abs(a[i].x-x)+abs(a[i].y-y)>a[i].t-t){
                printf("No");
                return 0;
            }
            long long f=a[i].t-t-abs(a[i].x-x)+abs(a[i].y-y);
            if(f%2==1){
            	printf("No");
                return 0;
            }
            x=a[i].x;
            y=a[i].y;
            t=a[i].t;
        }
        printf("Yes");
        return 0;
    }

2022/9/3 22:04
加载中...