Editorial for Team Selection
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=100010; var n,re:longint; a,b,c,f,d:array[1..maxn] of longint; procedure rf; var i,t:longint; begin readln(n); for i:=1 to n do begin read(a[i]); d[a[i]]:=i; end; for i:=1 to n do begin read(t); b[d[t]]:=i; end; for i:=1 to n do begin read(t); c[d[t]]:=i; end; end; function last(i:longint):longint; begin last:=i and (-i); end; function calc(i:longint):longint; var t:longint; begin t:=maxlongint; while i>0 do begin if (f[i]<t) and (f[i]>0) then t:=f[i]; i:=i-last(i); end; calc:=t; end; procedure put(i,v:longint); begin while i<=maxn do begin if (f[i]>v) or (f[i]=0) then f[i]:=v else break; i:=i+last(i); end; end; procedure pr; var i:longint; begin for i:=1 to n do begin if calc(b[i])<c[i] then inc(re); put(b[i],c[i]); end; writeln(n-re); end; begin rf; pr; end.
Code mẫu của ladpro98
program nkteam; uses math; type e=record x,y,z:longint; end; const maxn=100005; oo=maxn; fi=''; var n,res,minZ:longint; it:array[0..4*maxn] of longint; a:array[0..maxn] of e; procedure input; var inp:text; i,c:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do begin read(inp,c); a[c].x:=i; end; for i:=1 to n do begin read(inp,c); a[c].y:=i; end; for i:=1 to n do begin read(inp,c); a[c].z:=i; end; close(inp); end; procedure swap(i,j:longint); var t:e; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure sort(l,r:longint); var i,j,p:longint; begin if l>=r then exit; i:=l;j:=r; p:=a[random(r-l+1)+l].x; repeat while a[i].x<p do inc(i); while a[j].x>p do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i);dec(j); end; until i>j; sort(l,j); sort(i,r); end; procedure update(k,l,r,i,v:longint); var m:longint; begin if (i<l) or (r<i) then exit; if l=r then begin it[k]:=min(it[k],v); exit; end; m:=(l+r) shr 1; update(2*k,l,m,i,v); update(2*k+1,m+1,r,i,v); it[k]:=min(it[2*k],it[2*k+1]); end; procedure get(k,l,r,i,j:longint); var m:longint; begin if (j<l) or (r<i) then exit; if (i<=l) and (r<=j) then begin minZ:=min(minZ,it[k]); exit; end; m:=(l+r) shr 1; get(2*k,l,m,i,j); get(2*k+1,m+1,r,i,j); end; procedure process; var i:longint; begin for i:=1 to 4*n do it[i]:=oo; for i:=1 to n do begin minZ:=oo; get(1,1,n,1,a[i].y); if minZ<a[i].z then inc(res); update(1,1,n,a[i].y,a[i].z); end; end; begin input; sort(1,n); process; write(n-res); end.
Code mẫu của RR
{$R+,Q+} PROGRAM NKTEAM; CONST FINP=''; FOUT=''; oo=1000000000; maxn=100000; VAR n,kq:longint; a,b,c,d,inA,inD,minC:array[1..maxn] of longint; procedure readInput; var f:text; i,u:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do begin read(f,u); a[u]:=i; end; for i:=1 to n do begin read(f,u); b[u]:=i; end; for i:=1 to n do begin read(f,u); c[u]:=i; end; close(f); end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure sortA(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin swap(a[i],a[j]); swap(b[i],b[j]); swap(c[i],c[j]); inc(i); dec(j); end; until i>j; if i<r then sortA(i,r); if l<j then sortA(l,j); end; procedure initD; var i:longint; begin for i:=1 to n do begin d[i]:=b[i]; inA[i]:=i; end; end; procedure sortD(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=d[(l+r) div 2]; repeat while d[i]<mid do inc(i); while d[j]>mid do dec(j); if i<=j then begin swap(d[i],d[j]); swap(inA[i],inA[j]); inc(i); dec(j); end; until i>j; if i<r then sortD(i,r); if l<j then sortD(l,j); end; procedure prepare; var i:longint; begin for i:=1 to n do begin minC[i]:=oo; inD[inA[i]]:=i; end; end; procedure writeOutput; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; function min2(a,b:longint):longint; begin if a<b then min2:=a else min2:=b; end; function get(u:longint):longint; var v,kq:longint; begin if u=0 then begin get:=oo; exit; end; kq:=minC[u]; v:=u-u and (u xor (u-1)); if v>0 then kq:=min2(kq,get(v)); get:=kq; end; procedure update(u,k:longint); var v:longint; begin minC[u]:=min2(minC[u],k); v:=u+u and (u xor (u-1)); if v<=n then update(v,k); end; procedure solve; var i,m:longint; begin kq:=0; for i:=1 to n do begin m:=get(inD[i]-1); if m>c[i] then inc(kq); update(inD[i],c[i]); end; end; BEGIN readInput; sortA(1,n); initD; sortD(1,n); prepare; solve; writeOutput; END.
Code mẫu của hieult
#pragma comment(linker, "/STACK:16777216") #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000001 #define maxn 100011 #define base 1000000000 #define modunlo 111539786 #define oo 1000000002 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define ull unsigned long long #define fi first #define se second double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long int64; struct team{ int a,b,c; team(){}; team(int _a, int _b, int _c){ a = _a, b = _b, c = _c; } bool operator <(team T)const{ return a < T.a; } }; team A[maxn]; int n, f[maxn], x; int get(int x){ int res = oo; while(x > 0){ res = min(res, f[x]); x -= x & -x; } return res; } void update(int x, int gt){ while(x <= 100000){ f[x] = min(f[x], gt); x += x & -x; } } int main(){ //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); scanf("%d",&n); for(int i = 0; i <= n; i++) f[i] = oo; for(int i = 1; i <= n; i++){ scanf("%d",&x); A[x].a = i;} for(int i = 1; i <= n; i++){ scanf("%d",&x); A[x].b = i;} for(int i = 1; i <= n; i++){ scanf("%d",&x); A[x].c = i;} sort(A + 1, A + n + 1); int kq = 0; for(int i = 1; i <= n; i++){ if(get(A[i].b) > A[i].c) kq ++; update(A[i].b, A[i].c); } printf("%d",kq); }
Code mẫu của ll931110
{$MODE DELPHI} program NKTEAM; const input = ''; output = ''; maxn = 100000; maxv = maxn * 100; var a1,a2,a3,tree: array[1..maxn] of integer; n,count: integer; procedure init; var f: text; i,k: integer; begin assign(f, input); reset(f); readln(f, n); for i := 1 to n do begin read(f, k); a1[k] := i; end; for i := 1 to n do begin read(f, k); a2[k] := i; end; for i := 1 to n do begin read(f, k); a3[k] := i; end; close(f); end; procedure sw(var x,y: integer); var z: integer; begin z := x; x := y; y := z; end; procedure swap(i,j: integer); begin sw(a1[i],a1[j]); sw(a2[i],a2[j]); sw(a3[i],a3[j]); end; procedure sort(l,h: integer); var i,j,p: integer; begin if l >= h then exit; i := l; j := h; p := a1[random(h - l + 1) + l]; repeat while a1[i] < p do inc(i); while a1[j] > p do dec(j); if i <= j then begin if i < j then swap(i,j); inc(i); dec(j); end; until i > j; sort(l,j); sort(i,h); end; procedure update(x,val: integer); begin while x <= maxn do begin if tree[x] > val then tree[x] := val; x := x + (x and -x); end; end; function calc(x: integer): integer; var r: integer; begin r := maxv; while x > 0 do begin if r > tree[x] then r := tree[x]; x := x - (x and -x); end; calc := r; end; procedure solve; var tmp,i: integer; begin count := 1; for i := 1 to maxn do tree[i] := maxv; update(a2[1],a3[1]); for i := 2 to n do begin tmp := calc(a2[i]); if tmp >= a3[i] then inc(count); update(a2[i],a3[i]); end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, count); close(f); end; begin init; sort(1,n); solve; printresult; end.
Code mẫu của khuc_tuan
const maxn = 100000 ; var result, n : longint ; a, b, c : array[1..maxn] of longint ; min : array[1..maxn] of longint ; okk : boolean ; procedure nhap; var i : longint ; begin read(n); for i:=1 to n do read( a[i], b[i], c[i]); end; function nhohon( i,j : longint ) : boolean ; begin if a[i]=a[j] then if b[i]=b[j] then nhohon := c[i]<c[j] else nhohon := b[i]<b[j] else nhohon := a[i]<a[j]; end; procedure sort( l, r : longint ); var i, j : longint ; m, t : longint ; begin i := l ; j := r ; m := (l+r) div 2; repeat while nhohon(i,m) do inc(i); while nhohon(m,j) do dec(j); if i<=j then begin if(m=i) then m:=j else if(m=j) then m:=i; t := a[i]; a[i] := a[j]; a[j] := t; t := b[i]; b[i] := b[j]; b[j] := t; t := c[i]; c[i] := c[j]; c[j] := t; inc(i); dec(j); end; until i>j; if(i<r) then sort(i,r); if(l<j) then sort(l,j); end; procedure update( id, va : longint ); begin while id<=n do begin if min[id]>va then min[id] := va; id := id + (id and (-id)) ; end; end; procedure check( id, va : longint ); begin while id>0 do begin if min[id]<va then begin okk := true; break; end; id := id - (id and (-id)); end; end; procedure xuly; var i : longint ; begin fillchar( min, sizeof(min), $3f); sort(1 , n); update( b[1], c[1]); result := 1; for i:=2 to n do begin okk := false ; check( b[i], c[i]); update( b[i], c[i]); if not okk then result := result + 1; end; end; procedure main; var i,t : integer ; begin //read(t); t := 1; for i:=1 to t do begin nhap; xuly; writeln( result); end; end; begin { assign( input, 't.t'); reset( input);} main; { close( input);} end.
Comments