QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464947#8209. Curly PalindromesyzhangWA 0ms3708kbC++142.0kb2024-07-06 16:20:462024-07-06 16:20:46

Judging History

This is the latest submission verdict.

  • [2024-07-06 16:20:46]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3708kb
  • [2024-07-06 16:20:46]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long 
#define N 105
using namespace std;
string val[N];
struct vec{
    int x,y;
}p[N];
vec operator - (const vec &a,const vec &b){
    return (vec){b.x-a.x,b.y-a.y};
}
ll cross(vec a,vec b){
    return 1ll*a.x*b.y-1ll*a.y*b.x;
}
vector<int> v[26];
int cnt[26],ans=1;
bool f=0;
void dfs(vec p1,vec p2,vec p3,vec p4,int len){
    if(f) return;
    ans=max(ans,len);
    for(int i=0;i<26;++i)
        for(int j=0;j<(int)v[i].size();++j)
            if(cross(p1-p[v[i][j]],p2-p1)>0&&cross(p4-p3,p[v[i][j]]-p4)>0&&cross(p[v[i][j]]-p4,p1-p[v[i][j]])>0)
                f=1;
    for(int i=0;i<26;++i)
        if(v[i].size()>=2){
            if(cross(p1-p[v[i][0]],p2-p1)>0&&cross(p4-p3,p[v[i][1]]-p4)>0)
                dfs(p[v[i][0]],p1,p4,p[v[i][1]],len+2);
            if(cross(p1-p[v[i][1]],p2-p1)>0&&cross(p4-p3,p[v[i][0]]-p4)>0)
                dfs(p[v[i][1]],p1,p4,p[v[i][0]],len+2);
        }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>p[i].x>>p[i].y>>val[i];
        ++cnt[val[i][0]-'a'];
        v[val[i][0]-'a'].push_back(i);
    }
    for(int i=0;i<26;++i) if(cnt[i]>2) {
        cout<<"Infinity";
        return 0;
    }
    for(int i=0;i<26;++i){
        for(int j=0;j<v[i].size();++j){
            for(int k=0;k<26;++k)
                if(v[k].size()==2){
                    if(cross(p[v[i][j]]-p[v[k][0]],p[v[k][1]]-p[v[i][j]])>0)
                        dfs(p[v[k][0]],p[v[i][j]],p[v[i][j]],p[v[k][1]],3);
                    if(cross(p[v[i][j]]-p[v[k][1]],p[v[k][0]]-p[v[i][j]])>0)
                        dfs(p[v[k][1]],p[v[i][j]],p[v[i][j]],p[v[k][0]],3);
                }
        }
        if(v[i].size()==2){
            dfs(p[v[i][0]],p[v[i][1]],p[v[i][0]],p[v[i][1]],2);
            dfs(p[v[i][1]],p[v[i][0]],p[v[i][1]],p[v[i][0]],2);
        }
    }
    if(f){
        cout<<"Infinity";
        return 0;
    }
    cout<<ans<<'\n';
    return 0;
}

詳細信息

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

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

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3616kb

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:

Infinity

result:

wrong answer 1st lines differ - expected: '2', found: 'Infinity'