QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320080#8209. Curly Palindromesucup-team266#AC ✓1ms3708kbC++142.6kb2024-02-03 13:39:272024-02-03 13:39:28

Judging History

This is the latest submission verdict.

  • [2024-02-03 13:39:28]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3708kb
  • [2024-02-03 13:39:27]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 998244353;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

const double eps = 1e-8;
inline int sign(double x){ return (x > eps ? +1 : (x < -eps ? -1 : 0)); }
struct vec{
	int x, y;
	vec(int _x = 0, int _y = 0){ x = _x, y = _y; }
};
inline vec operator -(vec lh, vec rh){ return vec(lh.x - rh.x, lh.y - rh.y); } // 向量减
inline ll Cross(vec lh, vec rh){ return 1ll * lh.x * rh.y - 1ll * lh.y * rh.x; } // 向量叉乘

int n;
vec a[111];
char c[111];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	rep(i, n) cin >> a[i].x >> a[i].y >> c[i];

	int ans = 1;

	rep(i, n) rep(j, n) if(i != j && c[i] == c[j])
		ans = 2;
	
	rep(i, n) rep(j, n) rep(k, n){
		//cout << c[i] << " "  << c[j] << "\n";
		//cout << Cross(a[i], a[j]) << "\n";
		if(Cross(a[i] - a[j], a[j] - a[k]) > 0 && Cross(a[j] - a[k], a[k] - a[i]) > 0 && Cross(a[k] - a[i], a[i] - a[j]) > 0 && c[i] == c[j]){
			cout << "Infinity\n";
			return 0;
		}
	}
	
	cout << ans << "\n";

	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

4
0 0 o
1 1 c
2 2 p
3 3 c

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

3
2 3 e
3 2 e
8 9 e

output:

Infinity

result:

ok single line: 'Infinity'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

3
0 0 p
1 1 c
2 2 o

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

3
1000000000 1000000000 a
0 1000000000 b
1000000000 0 a

output:

Infinity

result:

ok single line: 'Infinity'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

5
10 0 a
20 0 b
30 0 c
41 0 d
42 0 e

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

6
999999999 1000000000 b
0 0 a
1 1 a
2 2 c
3 3 d
4 4 e

output:

Infinity

result:

ok single line: 'Infinity'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1
52524 6287 o

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

100
620277501 352211578 a
588745387 204868067 a
279087773 862840409 a
368942847 32429835 a
986161321 811576403 a
108066135 22119129 a
854047430 512772131 a
196877261 824967276 a
467809712 903492464 a
549499819 662329823 a
358024530 364859507 a
323528347 87306983 a
346602511 829302399 a
216164493 243...

output:

Infinity

result:

ok single line: 'Infinity'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

100
964906060 545884156 b
525844995 678718384 a
767874103 529057847 b
335899480 961060244 b
458611128 578152716 b
449062933 779433747 a
672526007 895103745 b
111902255 436806217 a
873636242 773662394 a
250185459 522336127 a
975489206 77297854 b
54583166 952092302 a
863604349 909716224 a
70170689 533...

output:

Infinity

result:

ok single line: 'Infinity'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

100
197441358 388148939 b
374082779 922588431 b
545855650 531926491 b
953289473 249626190 a
997668672 445922624 b
941714598 963970889 a
252303702 946260915 c
705178416 744961339 a
889814639 633539049 b
526449032 53699804 b
937365752 742338401 b
294384909 349114633 b
245948038 979810742 c
46734037 30...

output:

Infinity

result:

ok single line: 'Infinity'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

100
388507460 599009943 b
222320564 871491185 b
323837196 829762427 d
202083245 906788357 c
200289725 313692532 c
65770043 517104251 d
905710326 292385376 b
3487284 126745388 b
495927620 829852193 b
97679895 880030775 b
677903935 407378948 d
534186652 672508037 b
964728216 976276332 b
391893605 5597...

output:

Infinity

result:

ok single line: 'Infinity'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

100
916010051 146307434 c
480623765 410328522 d
28189815 127598363 c
745844310 195354303 c
739347268 591527857 d
484792781 775270322 b
190520730 638509838 d
6828862 434900510 b
512106017 321132628 e
668910759 411394452 b
639780481 72419495 a
773988394 364497659 c
347071905 341338141 d
368456952 5180...

output:

Infinity

result:

ok single line: 'Infinity'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

100
86229674 966475154 g
188905509 869037044 j
206431319 885238671 g
384203494 608011484 b
94907195 845681979 j
93491181 751753218 f
658592436 874867662 j
390873056 182636414 b
313350178 5306341 j
964520327 884419573 c
616180319 281427186 e
506244230 796896398 b
427455351 844237339 f
78090262 517379...

output:

Infinity

result:

ok single line: 'Infinity'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

100
215977786 124594064 t
330805101 191632694 a
89113834 355297431 h
763543468 766857893 i
129574380 326152621 t
980011509 580824171 l
593104211 610936942 p
433305160 169599834 n
169733556 636573400 d
529043807 454466372 h
898931244 35490902 l
277816100 810116698 c
35985918 405195648 i
188992394 893...

output:

Infinity

result:

ok single line: 'Infinity'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

100
708120351 620407913 n
535329934 654852971 t
609745260 478749536 q
362094763 276915210 s
280981242 647870195 n
936373080 162431905 h
260497437 466345348 o
181689176 124319222 n
488142303 321448453 b
39367382 527550314 k
301142721 730766894 n
126691970 634927413 k
412986447 268439483 x
227790067 4...

output:

Infinity

result:

ok single line: 'Infinity'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

26
526735598 478961006 a
531191531 475454507 b
378204498 595844306 c
442072871 545584487 d
525250287 480129839 e
498514689 501168833 f
568324306 446233682 g
470293780 523376660 h
554956507 456753179 i
455440670 535064990 j
397513541 580649477 k
612883636 411168692 l
513367799 489480503 m
465837847 5...

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

100
548848602 549471818 a
320148329 317853761 b
508881564 508994876 c
704275972 706882148 d
371217322 369574298 e
597697204 598943636 f
624341896 625928264 g
380098886 378569174 h
313487156 311107604 i
553289384 553969256 j
466694135 466269215 k
406743578 405553802 l
488898045 488756405 m
653206979 ...

output:

2

result:

ok single line: '2'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

100
509098504 507901696 w
513647756 511852544 t
638752186 620500864 f
565964154 557287296 e
438585098 446663552 s
283910530 312334720 l
702441714 675812736 g
295283660 322211840 h
561414902 553336448 b
434035846 442712704 g
688793958 663960192 n
447683602 454565248 o
320304546 343941504 c
540943268 ...

output:

2

result:

ok single line: '2'

Extra Test:

score: 0
Extra Test Passed