网站制作报价被哪些因素影响,宁波市江北区建设局网站,百度指数查询官网入口登录,用响应式做旧书网站NEERC 17 Problem I. Interactive Sort
Solution
当写了两倍正解的代码使用了两倍于正解的操作步数……
刚开始的想法是求出一个bbb#xff0c;再求出一个aaa#xff0c;依次轮换#xff0c;分别维护当前知道确定值的a,ba,ba,b的有序序列#xff0c;然后求aaa就在bbb的有…NEERC 17 Problem I. Interactive Sort
Solution
当写了两倍正解的代码使用了两倍于正解的操作步数……
刚开始的想法是求出一个bbb再求出一个aaa依次轮换分别维护当前知道确定值的a,ba,ba,b的有序序列然后求aaa就在bbb的有序序列里二分确定大致范围再暴力求出当前数的大小并更新bbb中每个数的上下界求bbb同理。
这样操作次数应该是O(nlgn)O(nlgn)O(nlgn)的然而常数太大了……需要接近40W40W40W次操作。
而正解则是上一个做法的一半。。。 我们依次用上述方法求出每一个bbb可以发现显然到最后aaa中的数的上下界相等可以唯一确定一个aaa所以大概只需要一半的操作步数了。
时间复杂度O(n2)O(n^2)O(n2)代码是O(n2lgn)O(n^2lgn)O(n2lgn)的多一个mapmapmap也没慢多少。
Code one
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
int example_a[MAXN],example_b[MAXN];
inline int read() { int x; scanf(%d,x); return x; }
inline char get_ch() { char c ; while (c!c!) scanf(%c,c); return c; }
inline char get_chxy(int x,int y) { return example_a[x]example_b[y]?:; }mapPR,int Map;
int la[MAXN],lb[MAXN],ra[MAXN],rb[MAXN],a[MAXN],b[MAXN],Ansa[MAXN],Ansb[MAXN],ida[MAXN],idb[MAXN],n,Num0;int get(int x,int y)
{if (Map.count(MP(x,y))) return Map[MP(x,y)];printf(? %d %d\n,x,y),fflush(stdout);return Map[MP(x,y)](get_ch());
}PR geta(int x)
{int l1,rx,L,R;while (lr){int mid(lr1)1;if (get(x,idb[mid])) lmid;else rmid-1;}if (!get(x,idb[l])) L1,Rb[l];else Lb[l],R(l1x?n:b[l1]);return MP((L1)?L1:L,(R1)?R-1:R);
}
void solvea(int t)
{int num0;PR xgeta(t);
// Num0;for (int j1;j(n1)1;j){if (rb[j]x.fi) num;if (lb[j]x.sex.firb[j]) numget(t,j),Num;}
// coutAQueryNum:Numendl;Ansa[t]a[t]num1,ida[t]t;for (int j1;j(n1)1;j)if (Map.count(MP(t,j))) {int pMap[MP(t,j)];if (!p) upmax(lb[j],Ansa[t]1);else upmin(rb[j],Ansa[t]-1);}while (ta[t]a[t-1]) swap(a[t],a[t-1]),swap(ida[t],ida[t-1]),t--;
}PR getb(int x)
{int l1,rx-1,L,R;while (lr){int mid(lr)1;if (get(ida[mid],x)) rmid;else lmid1;}if (x1) L1,Rn;else if (!get(ida[r],x)) La[r],Rn;else L(r1?1:a[r-1]),Ra[r];return MP((!(L1))?L1:L,(!(R1))?R-1:R);
}
void solveb(int t)
{int num0;PR xgetb(t);
// Num0;for (int j1;jn1;j){if (ra[j]x.fi) num;if (la[j]x.sex.fira[j]) num(!get(j,t)),Num;}
// coutBQueryNum:Num x.fi x.seendl;Ansb[t]b[t]num1|1,idb[t]t;for (int j1;jn1;j)if (Map.count(MP(j,t))) {int pMap[MP(j,t)];if (!p) upmin(ra[j],Ansb[t]-1);else upmax(la[j],Ansb[t]1);}while (tb[t]b[t-1]) swap(b[t],b[t-1]),swap(idb[t],idb[t-1]),t--;
}
signed main()
{nread();srand(time(0));for (int i1;in1;i) example_a[i]i*2;for (int i1;i(n1)1;i) example_b[i]i*2-1;random_shuffle(example_a1,example_a(n1)1);random_shuffle(example_b1,example_b((n1)1)1);for (int i1;in/2;i) la[i]2,ra[i]n-(n1);for (int i1;i(n1)/2;i) lb[i]1,rb[i]n-((n1)^1);for (int i1,l,r;in/2;i) solveb(i),solvea(i);if (n1) solveb((n1)1);putchar(!);for (int i1;in/2;i) printf( %d,Ansa[i]);for (int i1;i(n1)/2;i) printf( %d,Ansb[i]);fflush(stdout);return 0;
}Code two
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
int example_a[MAXN],example_b[MAXN];
inline int read() { int x; scanf(%d,x); return x; }
inline char get_ch() { char c ; while (c!c!) scanf(%c,c); return c; }
inline char get_chxy(int x,int y) { return example_a[x]example_b[y]?:; }mapPR,int Map;
int la[MAXN],ra[MAXN],a[MAXN],b[MAXN],Ansb[MAXN],ida[MAXN],f[MAXN],n,Num0;int get(int x,int y)
{if (Map.count(MP(x,y))) return Map[MP(x,y)];printf(? %d %d\n,x,y),fflush(stdout);return Map[MP(x,y)](get_ch());
}
PR getb(int x)
{int num0;for (int i1;in1;i) f[i]0;for (int i1;in1;i) f[la[i]1]i;for (int i1;in1;i) if (f[i]) ida[num]f[i],a[num]la[f[i]],b[num]ra[f[i]];int l1,rnum,L,R;while (lr){Num;int mid(lr)1;if (get(ida[mid],x)) rmid;else lmid1;}if (!get(ida[r],x)) La[r],Rn;else L(r1?1:a[r-1]),Rb[r];return MP((!(L1))?L1:L,(!(R1))?R-1:R);
}
void solveb(int t)
{int num0;PR xgetb(t);for (int j1;jn1;j){if (ra[j]x.fi) num;if (la[j]x.sex.fira[j]) num(!get(j,t)),Num;}Ansb[t]num1|1;for (int j1;jn1;j)if (Map.count(MP(j,t))) {int pMap[MP(j,t)];if (!p) upmin(ra[j],Ansb[t]-1);else upmax(la[j],Ansb[t]1);}
}
signed main()
{nread();if (n1) { printf(! 1\n); return 0; }for (int i1;in/2;i) la[i]2,ra[i]n-(n1);for (int i1,l,r;in/2;i) solveb(i);if (n1) solveb((n1)1);putchar(!);for (int i1;in/2;i) printf( %d,la[i]);for (int i1;i(n1)/2;i) printf( %d,Ansb[i]);fflush(stdout);return 0;
}
