Editorial for VOI 14 Bài 1 - Con đường Tùng Trúc
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 happyboy99x
#include<algorithm> #include<vector> #include<cstdio> using namespace std; const int INF = (int) 1e9 + 7; int main() { int n, a, b; scanf("%d %d %d", &n, &a, &b); vector<pair<int, int> > tree (n); for(int i = 0; i < n; ++i) { scanf("%d %d", &tree[i].first, &tree[i].second); } sort(tree.begin(), tree.end()); vector<int> pos1 (n), pos2 (n); int x = 0, y = 0, res = INF; for(int i = 0; i < n; ++i) { if(tree[i].second == 1) { pos1[x++] = tree[i].first; } else { pos2[y++] = tree[i].first; } if(x >= a && y >= b) { res = min(res, tree[i].first - min(pos1[x - a], pos2[y - b])); } } printf("%d\n", res == INF ? -1 : res); return 0; }
Code mẫu của ladpro98
program minroad; uses math; type e=record x,t:longint; end; const fi = ''; fo = ''; maxN = 300050; var a :array[1..maxN] of e; truc,tung :array[0..maxN] of longint; n,res,p,q :longint; procedure input; var f:text; i:longint; begin assign(f,fi); reset(f); readln(f,n,p,q); for i:=1 to n do readln(f,a[i].x,a[i].t); close(f); 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 p,i,j:longint; begin if l>=r then exit; p:=a[random(r-l+1)+l].x; i:=l;j:=r; 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 init; var i:longint; begin for i:=1 to n do if a[i].t=1 then begin tung[i]:=tung[i-1]+1; truc[i]:=truc[i-1]; end else begin tung[i]:=tung[i-1]; truc[i]:=truc[i-1]+1; end; end; procedure process; var i,j:longint; begin res:=high(longint); j:=2; for i:=1 to n do begin while (j<=n) and (((tung[j]-tung[i-1])<p) or ((truc[j]-truc[i-1])<q)) do inc(j); if j<=n then res:=min(res,a[j].x-a[i].x); end; end; procedure output; var f:text; begin assign(f,fo); rewrite(f); if res=high(longint) then res:=-1; write(f,res); close(f); end; begin input; sort(1,n); init; process; output; end.
Code mẫu của RR
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define DEBUG(x) { cout << #x << " = "; cout << x << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } using namespace std; //Buffer reading int INP,AM,REACHEOF; const int BUFSIZE = (1<<12) + 17; char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp && !REACHEOF) { \ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const int MN = 300111; const int oo = 1000111000; int n, a, b, c1[MN], c2[MN]; pair<int,int> x[MN]; int main() { ios :: sync_with_stdio(false); cin >> n >> a >> b; FOR(i,1,n) cin >> x[i].first >> x[i].second; sort(x+1, x+n+1); FOR(i,1,n) { c1[i] = c1[i-1] + (x[i].second == 1); c2[i] = c2[i-1] + (x[i].second == 2); } int best = oo; FOR(i,1,n) { if (c1[i] < a || c2[i] < b) continue; int left = 1, right = i, res = 1; while (left <= right) { int mid = (left + right) >> 1; if (c1[i] - c1[mid-1] >= a && c2[i] - c2[mid-1] >= b) { res = mid; left = mid + 1; } else right = mid - 1; } best = min(best, x[i].first - x[res].first); } if (best == oo) cout << -1; else cout << best; cout << endl; return 0; }
Comments