QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320056#8209. Curly Palindromesucup-team2112#AC ✓1ms3820kbC++176.6kb2024-02-03 13:30:362024-02-03 13:30:37

Judging History

This is the latest submission verdict.

  • [2024-02-03 13:30:37]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3820kb
  • [2024-02-03 13:30:36]
  • Submitted

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;
 
template<class A, class B> string to_string(const pair<A, B> &p);
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p);
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<size_t L> string to_string(const bitset<L> &x) { return x.to_string(); }
template<class A, class T = typename A::value_type> string to_string(const A &v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if (0) puts("No effect.")
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

/**
 * Author: Yuhao Yao
 * Date: 22-10-31
 * Description: Class to handle points in 2D-plane. Avoid using $T = int$. 
 * Status:
 *  project_to_line (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
 *  dis_to_line (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
 *  dis_to_seg (double) tested on https://acm.hdu.edu.cn/showproblem.php?pid=6419.
 */
template<class T> 
struct Point {
	using P = Point; /// start-hash
	using type = T;
	static constexpr T eps = 1e-9;
	static constexpr bool isInt = is_integral_v<T>;
	static int sgn(T x) { return (x > eps) - (x < -eps); }
	static int cmp(T x, T y) { return sgn(x - y); }

	T x, y;

	P operator +(P b) const { return P{x + b.x, y + b.y}; }
	P operator -(P b) const { return P{x - b.x, y - b.y}; }
	P operator *(T b) const { return P{x * b, y * b}; }
	P operator /(T b) const { return P{x / b, y / b}; }
	bool operator ==(P b) const { return cmp(x, b.x) == 0 && cmp(y, b.y) == 0; }
	bool operator <(P b) const { return cmp(x, b.x) == 0 ? cmp(y, b.y) < 0: x < b.x; }

	T len2() const { return x * x + y * y; }
	T len() const { return sqrt(x * x + y * y); }
	P unit() const {
		if (isInt) return *this; // for long long
		else return len() <= eps ? P{} : *this / len(); // for double / long double;
	}

	// dot and cross may lead to big relative error for imprecise point when the result is relatively smaller than the input magnitude.
	T dot(P b) const { return x * b.x + y * b.y; }
	T cross(P b) const { return x * b.y - y * b.x; }
	/// end-hash

	int is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); } /// start-hash
	
	// return -1 if a has smaller pollar; return 1 if a has a larger pollar; return 0 o.w.
	// Taking unit makes it slower but it performs as atan2.
	static int argcmp(P a, P b) {
		if (a.is_upper() != b.is_upper()) return a.is_upper() - b.is_upper();
		return sgn(b.cross(a));
	} /// end-hash

	P rot90() const { return P{-y, x}; }
	P rot270() const { return P{y, -x}; }
	
	// Possible precision error: 
	// Absolute error is multiplied by the magnitude while the resulting coordinates can have 0 as magnitude!
	P rotate(T theta) const { /// start-hash
		P a{cos(theta), sin(theta)};
		return P{x * a.x - y * a.y, x * a.y + y * a.x};
	} /// end-hash

	// Returns the signed distance to line $ab$. $a$, $b$ should be distinct.
	T dis_to_line(P a, P b) const { /// start-hash
		assert((a - b).len2() > P::eps);
		if (isInt) return (*this - a).cross(b - a);
		else return (*this - a).cross(b - a) / (b - a).len();
	} /// end-hash
	
	// Check if it is on line $ab$. $a$, $b$ should be distinct.
	bool on_line(P a, P b) const {  /// start-hash
		return sgn(dis_to_line(a, b)) == 0;
	}  /// end-hash

	// Returns the signed projected length onto line $ab$. Return 0 if $a = b$.
	T project_len(P a, P b) const { /// start-hash
		if (isInt) return (*this - a).dot(b - a);
		else if (a == b) return 0;
		else return (*this - a).dot(b - a) / (b - a).len();
	} /// end-hash
	
	// Calculate the projection to line $ab$. Return $a$ when $a = b$.
	// Only for double / long double.
	P project_to_line(P a, P b) const { /// start-hash
		return a + (b - a).unit() * project_len(a, b);
	} /// end-hash
		
	// Returns the distance to line segment $ab$. Safe when $a = b$.
	// Only for double / long double.
	T dis_to_seg(P a, P b) const { /// start-hash
		if (project_len(a, b) <= eps) return (*this - a).len();
		if (project_len(b, a) <= eps) return (*this - b).len();
		return fabs(dis_to_line(a, b));
	} /// end-hash
	
	// Check if it is on segment ab. Safe when a == b.
	bool on_seg(P a, P b) const {  /// start-hash
		return dis_to_seg(a, b) <= eps; 
	}  /// end-hash
	
	friend string to_string(P p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }
};


int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	using T = ll;
	using P = Point<T>;
	
	int n; cin >> n;
	vector<P> as(n);
	vector<string> cs(n);

	rep(i, 0, n - 1) {
		cin >> as[i].x >> as[i].y >> cs[i];
	}
	map<string, int> cnt;
	for (auto s : cs) cnt[s]++;
	bool ok = true;
	for (auto &[s, c] : cnt) if (c > 1) ok = false;
	if (ok) {
		puts("1");
	} else {
		if (n == 2) {
			puts("2");
		} else {
			bool col = true;
			rep(i, 2, n - 1) {
				if ((as[i] - as[0]).cross(as[1] - as[0]) != 0) {
					col = false;
				}
			}
			if (col) {
				puts("2");
			} else {
				puts("Infinity");
			}
		}
	}
	return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3752kb

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: 1ms
memory: 3528kb

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: 3608kb

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: 3536kb

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: 3492kb

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: 3568kb

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: 3604kb

input:

1
52524 6287 o

output:

1

result:

ok single line: '1'

Test #8:

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

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: 3588kb

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: 3756kb

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: 1ms
memory: 3548kb

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: 3612kb

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: 3564kb

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: 3588kb

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: 3620kb

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: 3540kb

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: 0ms
memory: 3540kb

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: 0ms
memory: 3820kb

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