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.

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

Please read the guidelines before commenting.

There are no comments at the moment.