QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#670092#9487. Vivid Colorsbulijiojiodibuliduo#RE 0ms4088kbC++173.1kb2024-10-23 20:26:402024-10-23 20:26:41

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 20:26:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4088kb
  • [2024-10-23 20:26:40]
  • 提交

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...

output:


result: