CF576C Points on Plane 构造
正解:构造
解题报告:
先放下传送门趴QAQ
话说我jio得这题好玄学啊,,,就是,我实在觉得我这题做得完美无缺了?可就是过不去,,,而且它告诉我的奇异错误是"wrong output format Unexpected end of file - int32 expected "我当场就爆哭出来了趴QAQ连错6次正确率啪叽啪叽掉啊QAQ
不管,不想做这题了,决定来摸下鱼把题解给写了QAQ
看到这题,自然而然就会想到,莫队,对趴
对它其实就是个,莫队的最前面的那个分块
正确性我不会分析但是根据我们之前学的莫队的芝士,莫队的时间复杂度是O(n√n),那么放这题就是1e9刚好卡着过
要注意一下的是我们还可以优化一点儿
就是如果单纯x单调增排然后内部y单调增排是不欧克的,会增加1e9
所以可以,奇偶块内部分别y单增单减排
没了
所以我到底哪里错了啊呜呜呜,,,一个月没碰电脑不会打莫队的老年选手是我了QAQ
放个代码趴QAQ
#include<bits/stdc++.h> using namespace std; #define ll long long #define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=1000000; ll n,lth; struct nod{ll x,y,id,bl;}gg[N]; inline ll read() { char ch=getchar();ll x=0;bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline bool cmp1(nod gd,nod gs){return gd.x<gs.x;} inline bool cmp2(nod gd,nod gs) { if(gd.bl!=gs.bl)return gd.bl<gs.bl; if(gd.bl&1)return gd.y<gs.y; return gd.y>gs.y; } int main() { n=read();rp(i,1,n)gg[i].x=read(),gg[i].y=read(),gg[i].id=i; lth=sqrt(n);sort(gg+1,gg+1+n,cmp1);rp(i,1,n)gg[i].bl=(i-1)/lth+1; sort(gg+1,gg+1+n,cmp2); rp(i,1,n)printf("%lld ",gg[i].id); return 0; }