Editorial for VM 11 Bài 01 - Pirate đãng trí

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

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define maxN 100100

using namespace std;

int n,deg[maxN],rest[maxN*3],mx[maxN*3];

void init(int nd,int l,int r)

{

if (l==r) rest[nd]=mx[nd]=deg[l];

else

{

int m=(l+r)>>1;

init(nd<<1,l,m);

init((nd<<1)+1,m+1,r);

mx[nd]=mx[(nd<<1)+1];

}

}

void decrease(int nd,int l,int r,int x,int y,int val)

{

if (l==x && r==y) rest[nd]-=val, mx[nd]-=val;

else

{

int m=(l+r)>>1;

if (x<=m) decrease(nd<<1,l,m,x,min(y,m),val);

if (m<y)

{

decrease((nd<<1)+1,m+1,r,max(x,m+1),y,val);

mx[nd]=mx[(nd<<1)+1]+rest[nd];

}

}

}

int getValue(int nd,int l,int r,int x)

{

if (l==r) return rest[nd];

int m=(l+r)>>1;

if (x<=m) return rest[nd]+getValue(nd<<1,l,m,x);

return rest[nd]+getValue((nd<<1)+1,m+1,r,x);

}

int findLeftmost(int nd,int l,int r,int x)

{

if (mx[nd]<x) return n;

if (l==r) return l;

int m=(l+r)>>1;

x-=rest[nd];

if (mx[nd<<1]>=x) return findLeftmost(nd<<1,l,m,x);

return findLeftmost((nd<<1)+1,m+1,r,x);

}

int main()

{

int x,y,test,pos;

cin >> test;

while (test--)

{

memset(rest,0,sizeof(rest));

memset(mx,0,sizeof(mx));

cin >> n;

int valid=1;

for (int i=0;i<n;i++) scanf("%d",&deg[i]);

sort(deg,deg+n);

init(1,0,n-1);

for (int i=0;i<n;i++)

{

x=getValue(1,0,n-1,i);

if (x+i>=n)

{

valid=0; break;

}

if (!x) continue;

decrease(1,0,n-1,i,i,x);

y=getValue(1,0,n-1,n-x);

if (!y)

{

valid=0; break;

}

pos=findLeftmost(1,0,n-1,y+1);

if (pos<n) decrease(1,0,n-1,pos,n-1,1);

x-=(n-pos);

pos=findLeftmost(1,0,n-1,y);

decrease(1,0,n-1,pos,pos+x-1,1);

}

cout << (valid?"YES":"NO") << endl;

}

return 0;

}


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 100005;

using namespace std;
int n, nTest;
int a[N];

struct fenwickTree {
int bit[N], n;
void reset(int _n) {
n = _n;
REP(i, 0, n)
bit[i] = 0;
}
void inc(int i, int v) {
for(++i; i <= n; i += i & -i)
bit[i] += v;
}
void inc(int i, int j, int v) {
inc(i, v); inc(j + 1, -v);
}
void dec(int i, int j) {
inc(i, -1); inc(j + 1, 1);
}
int at(int i) {
int ret = 0;
for(++i; i; i -= i & -i)
ret += bit[i];
return ret;
}
} BIT;

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> nTest;
while (nTest--) {
cin >> n;
bool NO = 0;
FOR(i, 0, n) {
cin >> a[i];
NO |= a[i] >= n;
}
if (NO) {
cout << "NO\n";
continue;
}
sort(a, a + n, greater<int>());
BIT.reset(n);
FOR(i, 0, n)
BIT.inc(i, i, a[i]);
FOR(i, 0, n) {
a[i] = BIT.at(i);
if (a[i] >= n - i || a[i] < 0) {
NO = 1; break;
}
if (a[i] == 0) continue;
int pos = i + a[i], L = pos, R = pos;
int last = BIT.at(pos);
int l = i + 1, r = pos;
while (l <= r) {
int mid = l + r >> 1;
if (BIT.at(mid) == last) {
L = mid; r = mid - 1;
}
else
l = mid + 1;
}
l = pos, r = n - 1;
while (l <= r) {
int mid = l + r >> 1;
if (BIT.at(mid) == last) {
R = mid; l = mid + 1;
}
else
r = mid - 1;
}
int len = pos - L + 1;
BIT.dec(i + 1, L - 1);
BIT.dec(R - len + 1, R);
}
if (!NO) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}


Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#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 FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#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;

int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
memset(BUF,0,sizeof BUF);\
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;\
}

const long double PI = acos((long double) -1.0);
const int MN = 100111;

int n, a[MN], s[MN];

int main() {
int ntest; GN(ntest);
while (ntest--) {
int n; GN(n);
FOR(i,1,n) {
GN(a[i]);
a[i] = -a[i];
}
sort(a+1, a+n+1);
FOR(i,1,n) {
a[i] = -a[i];
s[i] = s[i-1] + a[i];
}

if (s[n] % 2) {
puts("NO");
continue;
}

bool ok = true;

int j = n;
FOR(i,1,n) {
long long ln = i*(i-1LL);
if (j < i) j = i;
while (j > i && a[j] < i) --j;

ln += i*(ll) (j-i);
ln += s[n] - s[j];

if (ln < s[i]) {
ok = false;
break;
}
}

if (ok) puts("YES");
else puts("NO");
}
return 0;
}


Code mẫu của hieult

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
//#include <conio.h>

using namespace std;

int test,n,a[111111];
long long tong[111111],A,B,u,k,f[111111];
bool kq;

int main(){
// freopen("VMDEGREE.in","r",stdin);
scanf("%d",&test);
for(int itest = 1;itest<=test;itest++){
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
a[0] = 0;
tong[0] = 0;
for(int i = 1;i<=n;i++) tong[i] = tong[i-1]+a[i];
u = a[n];
// for(int i = 1;i<=n;i++)
//  printf("%d %lld\n",a[i],tong[i]);
for(int i = n-1;i>=0;i--){
for(int j = u;j>a[i];j--)
f[j] = i+1;
u = a[i];
}
f[0] = 1;
//for(int i = 1;i<=n;i++) printf("*******%d\n",f[i]);
if(tong[n]%2==1){
printf("NO\n");
continue;
}
kq = true;
for(int i = n;i>=1;i--){
k = n-i+1;
A = tong[n]-tong[i-1];
B = k*(k-1);
if(f[k]<i){
B+=k*(i-f[k])+tong[f[k]-1];
}
else B+=k*(i-1);
// printf("______%lld %lld %lld\n",k,A,B);
if(A>B){
kq = false;
break;
}
}
if(kq) printf("YES\n");
else printf("NO\n");
}
//getch();
}