QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670092 | #9487. Vivid Colors | bulijiojiodibuliduo# | RE | 0ms | 4088kb | C++17 | 3.1kb | 2024-10-23 20:26:40 | 2024-10-23 20:26:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
//typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef long long db;
const db EPS = 0;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
};
int cmp_ang(P a,P b) {
if (a.quad()!=b.quad()) return a.quad()<b.quad()?1:-1;
return sign(a.det(b));
}
const int N=2010;
struct evt {
P dir;
int s,t;
};
bool operator < (evt a,evt b) {
return cmp_ang(a.dir,b.dir)==1;
}
int n,ord[N],rk[N];
P p[N],sp[N];
ll ans[N];
int main() {
scanf("%d",&n);
rep(i,1,n+1) {
int R,G,B;
scanf("%d%d%d",&R,&G,&B);
p[i]={3*R-(R+G+B),3*G-(R+G+B)};
//printf("%lld %lld\n",p[i].x,p[i].y);
}
vector<evt> ev;
rep(i,1,n+1) rep(j,1,n+1) if (!(p[i]==p[j])) {
ev.pb({p[j]-p[i],i,j});
}
sort(all(ev));
rep(i,1,n+1) ord[i]=i;
sort(ord+1,ord+n+1,[&](int a,int b){
return p[a].y<p[b].y||(p[a].y==p[b].y&&p[a].x<p[b].x);
});
auto eval=[&](P a) {
return a.x*a.x+a.y*a.y+(a.x+a.y)*(a.x+a.y);
};
rep(i,1,n+1) rk[ord[i]]=i;
rep(i,1,n+1) {
sp[i]=sp[i-1]+p[ord[i]];
ans[i]=max(ans[i],eval(sp[i]));
}
//rep(i,1,n+1) {
// printf("%d\n",rk[i]);
//}
rep(i,0,SZ(ev)) {
int j=i;
while (j<SZ(ev)&&cmp_ang(ev[i].dir,ev[j].dir)==0) {
++j;
}
rep(l,i,j) {
//printf("swap %d %d %d %d\n",ev[l].s,ev[l].t,rk[ev[l].s],rk[ev[l].t]);
assert(rk[ev[l].t]<rk[ev[l].s]);
}
//puts("---");
sort(ev.begin()+i,ev.begin()+j,[&](const evt &a,const evt &b) {
return rk[a.s]-rk[a.t]<rk[b.s]-rk[b.t];
});
rep(l,i,j) {
//printf("swap? %d %d %d %d\n",ev[l].s,ev[l].t,rk[ev[l].s],rk[ev[l].t]);
assert(rk[ev[l].t]+1==rk[ev[l].s]);
int u=ev[l].t,v=ev[l].s,k=rk[u];
rk[u]=k+1; rk[v]=k;
sp[k]=sp[k-1]+p[v];
ans[k]=max(ans[k],eval(sp[k]));
}
i=j-1;
}
rep(i,1,n+1) {
ll ret=ans[i]%mod*powmod(27*i*i,mod-2)%mod;
printf("%lld\n",ret);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4088kb
input:
3 180 0 0 0 180 180 0 0 180
output:
7200 5400 800
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
6 30594 32322 46262 63608 59020 98436 90150 32740 67209 82886 4627 54813 3112 67989 74995 60872 9967 9051
output:
715162883 838096208 930330061 405079896 880764907 526006962
result:
ok 6 tokens
Test #3:
score: -100
Runtime Error
input:
144 41472 41434 41317 16965 16900 17440 65702 65688 65497 15829 15900 15359 186620 186555 186425 22130 22030 22145 22995 23022 23320 54430 54525 54770 145816 145739 146046 106008 106083 106073 84481 84531 84306 162468 162563 162313 144375 144342 144210 68596 68548 68201 124014 124100 123649 137878 1...