QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566033#7725. Just Sum Two NumbersCrysflyAC ✓6ms7192kbC++144.5kb2024-09-15 22:54:592024-09-15 22:55:00

Judging History

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

  • [2024-09-15 22:55:00]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:7192kb
  • [2024-09-15 22:54:59]
  • 提交

answer

///////////////////////////////////////////////////////
#include <stdio.h>
#include <array>
#include <random>
#include <queue>
std::mt19937_64 rng(0x3d03d);
#include <math.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#define ld(x) printf("%d\n",x)
#define int long long
using std::vector;
using vi=vector<int>;
using pi=std::pair<int,int>;
using vpi=vector<pi>;
#define x first
#define y second
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
char a[1005][1005],b[1005][1005];
char s[1005][1005];
int res=-5;
void find(vpi v)
{
    vi cnt(v.size()+2),mn(cnt.size(),1e9),xx(cnt.size());
    for(auto[x,y]:v)cnt[x]++,mn[x]=min(mn[x],y),xx[x]=max(xx[x],y);
    for(int i=0;i<mn.size();i++)
    {
        if(mn[i]<=xx[i]&&xx[i]-mn[i]+1!=cnt[i])
        {
            res+=5;
            return;
        }
    }
    int mx=0;
    for(auto t:cnt)mx=max(mx,t);
    int tot=0,qwq=0;
    for(auto t:cnt)
        tot+=t>0,qwq+=t>mx*2/3;
    if(qwq>tot*2/3)res++;
    else res+=5;
}
namespace qwq{
    int n;
#define ben pi
// ben *p;
vpi p;
ben s[10005];
double check(ben a1,ben a2,ben b1,ben b2)//妫€鏌ュ弶绉槸鍚﹀ぇ浜�0锛屽鏋滄槸a灏遍€嗘椂閽堣浆鍒癰 
{
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double d(ben p1,ben p2)//涓ょ偣闂磋窛绂汇€傘€傘€� 
{
    return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(ben p1,ben p2)//鎺掑簭鍑芥暟锛岃繖涓嚱鏁板埆鍐欓敊浜嗭紝瑕佷笉鐒跺姛浜忎竴绡� 
{
    double tmp=check(p[1],p1,p[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&d(p[0],p1)<d(p[0],p2)) 
		return 1;
    return 0;
}
int main(vpi A,int N)
{
	p=A;n=N;
    // scanf("%d",&n);
    double mid;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(i!=1&&p[i].y<p[1].y)//杩欐槸鏄幓閲� 
        {
            mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
            mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
        }
    } 
    sort(p.begin()+2,p.begin()+1+n,cmp);//绯荤粺蹇帓 
    s[1]=p[1];//鏈€浣庣偣涓€瀹氬湪鍑稿寘閲� 
    int cnt=1;
    for(int i=2;i<=n;i++)
    {
        while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0) //鍒ゆ柇鍓嶉潰鐨勪細涓嶄細琚涪璧帮紝濡傛灉琚涪璧伴偅涔堝嚭鏍�
			cnt--;
        cnt++;
        s[cnt]=p[i];
    }
    s[cnt+1]=p[1];//鏈€鍚庝竴涓偣鍥炲埌鍑稿寘璧风偣
    double ans=0; 
    // for(int i=1;i<=cnt;i++) printf("(%d,%d)\n",s[i].x,s[i].y);
    // for(int i=1;i<=n;i++) printf("(%d,%d)\n",p[i].x,p[i].y);
    for(int i=2;i<=cnt;i++) 
    {
        int x1=s[1].x-s[i].x;
        int y1=s[1].y-s[i].y;
        int x2=s[1].x-s[i+1].x;
        int y2=s[1].y-s[i+1].y;
        ans+=fabs(x1*y2-x2*y1)/2;
    }
		// ans+=d(s[i],s[i+1]);//鐒跺悗s閲屽瓨濂戒簡鍑稿寘搴忓垪锛屽彧闇€瑕佹妸涓や袱璺濈绱姞灏辫
    // printf("%.2lf %d\n",ans,n);
    if(n>ans*0.91)res+=1;
    else res+=5;
    return 0;
}
}
signed main()
{
	int n=read(),m=read();
    for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(a[i][j]=='#')
        {
            std::queue<pi>q;
            q.push({i,j});
            a[i][j]='.';
            vpi v={{0,0}};
            while(!q.empty())
            {
                pi u=q.front();q.pop();
                v.push_back(u);
                for(auto [dx,dy]:(vpi){{1,0},{-1,0},{0,1},{0,-1}})
                {
                    if(a[u.first+dx][u.second+dy]=='#')
                        a[u.first+dx][u.second+dy]='.',
                        q.push({u.first+dx,u.second+dy});
                }
            }
            // for(auto &[x,y]:v)x-=i-1;
            // find(v);
            qwq::main(v,v.size()-1);
        }
    printf("%d\n",res);
	fprintf(stderr,"%.12lf\n",1.*clock()/CLOCKS_PER_SEC);
    // for(int i=1;i<=n;i++)
    //     for(int j=1;j<=m;j++)
    //         if(a[i][j-1]=='#'&&a[i][j+1]=='#'&&a[i-1][j]=='#'&&a[i+1][j]=='#')
    //             b[i][j]=1;
    // for(int i=1;i<=n;i++)
    //     for(int j=1;j<=m;j++)
    //         if(b[i][j])a[i][j]='.';
    // for(int i=1;i<=n;i++)puts(a[i]+1);
	return 0;
}

详细

Test #1:

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

input:

100 354
.......................................................................................................................................................................................................................................................................................................

output:

17

result:

ok 1 number(s): "17"

Test #2:

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

input:

135 269
.............................................................................................................................................................................................................................................................................
.........................

output:

14

result:

ok 1 number(s): "14"

Test #3:

score: 0
Accepted
time: 2ms
memory: 4592kb

input:

294 451
.......................................................................................................................................................................................................................................................................................................

output:

18

result:

ok 1 number(s): "18"

Test #4:

score: 0
Accepted
time: 2ms
memory: 6080kb

input:

234 701
.......................................................................................................................................................................................................................................................................................................

output:

32

result:

ok 1 number(s): "32"

Test #5:

score: 0
Accepted
time: 4ms
memory: 5200kb

input:

888 585
.......................................................................................................................................................................................................................................................................................................

output:

49

result:

ok 1 number(s): "49"

Test #6:

score: 0
Accepted
time: 2ms
memory: 6216kb

input:

579 350
.......................................................................................................................................................................................................................................................................................................

output:

26

result:

ok 1 number(s): "26"

Test #7:

score: 0
Accepted
time: 4ms
memory: 6440kb

input:

884 910
.......................................................................................................................................................................................................................................................................................................

output:

59

result:

ok 1 number(s): "59"

Test #8:

score: 0
Accepted
time: 4ms
memory: 6632kb

input:

652 717
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #9:

score: 0
Accepted
time: 3ms
memory: 6900kb

input:

568 468
.......................................................................................................................................................................................................................................................................................................

output:

29

result:

ok 1 number(s): "29"

Test #10:

score: 0
Accepted
time: 5ms
memory: 6288kb

input:

923 959
.......................................................................................................................................................................................................................................................................................................

output:

61

result:

ok 1 number(s): "61"

Test #11:

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

input:

361 295
.......................................................................................................................................................................................................................................................................................................

output:

21

result:

ok 1 number(s): "21"

Test #12:

score: 0
Accepted
time: 4ms
memory: 6092kb

input:

712 929
.......................................................................................................................................................................................................................................................................................................

output:

50

result:

ok 1 number(s): "50"

Test #13:

score: 0
Accepted
time: 6ms
memory: 5148kb

input:

929 970
.......................................................................................................................................................................................................................................................................................................

output:

64

result:

ok 1 number(s): "64"

Test #14:

score: 0
Accepted
time: 2ms
memory: 4472kb

input:

394 346
.......................................................................................................................................................................................................................................................................................................

output:

24

result:

ok 1 number(s): "24"

Test #15:

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

input:

418 578
.......................................................................................................................................................................................................................................................................................................

output:

28

result:

ok 1 number(s): "28"

Test #16:

score: 0
Accepted
time: 2ms
memory: 6680kb

input:

457 499
.......................................................................................................................................................................................................................................................................................................

output:

27

result:

ok 1 number(s): "27"

Test #17:

score: 0
Accepted
time: 5ms
memory: 6356kb

input:

985 955
.......................................................................................................................................................................................................................................................................................................

output:

63

result:

ok 1 number(s): "63"

Test #18:

score: 0
Accepted
time: 3ms
memory: 6112kb

input:

209 704
.......................................................................................................................................................................................................................................................................................................

output:

30

result:

ok 1 number(s): "30"

Test #19:

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

input:

837 156
............................................................................................................................................................
..........................................................................................................................................

output:

37

result:

ok 1 number(s): "37"

Test #20:

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

input:

198 126
..............................................................................................................................
..............................................................................................................................
.........................................

output:

3

result:

ok 1 number(s): "3"

Test #21:

score: 0
Accepted
time: 4ms
memory: 5096kb

input:

996 684
.......................................................................................................................................................................................................................................................................................................

output:

57

result:

ok 1 number(s): "57"

Test #22:

score: 0
Accepted
time: 5ms
memory: 6504kb

input:

803 985
.......................................................................................................................................................................................................................................................................................................

output:

65

result:

ok 1 number(s): "65"

Test #23:

score: 0
Accepted
time: 5ms
memory: 6468kb

input:

948 820
.......................................................................................................................................................................................................................................................................................................

output:

62

result:

ok 1 number(s): "62"

Test #24:

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

input:

470 242
..................................................................................................................................................................................................................................................
....................................................

output:

19

result:

ok 1 number(s): "19"

Test #25:

score: 0
Accepted
time: 3ms
memory: 7192kb

input:

967 248
........................................................................................................................................................................................................................................................
..............................................

output:

49

result:

ok 1 number(s): "49"

Test #26:

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

input:

323 198
......................................................................................................................................................................................................
................................................................................................

output:

17

result:

ok 1 number(s): "17"

Test #27:

score: 0
Accepted
time: 2ms
memory: 4908kb

input:

623 385
.......................................................................................................................................................................................................................................................................................................

output:

31

result:

ok 1 number(s): "31"

Test #28:

score: 0
Accepted
time: 5ms
memory: 7172kb

input:

955 959
.......................................................................................................................................................................................................................................................................................................

output:

65

result:

ok 1 number(s): "65"

Test #29:

score: 0
Accepted
time: 4ms
memory: 5100kb

input:

987 745
.......................................................................................................................................................................................................................................................................................................

output:

56

result:

ok 1 number(s): "56"

Test #30:

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

input:

328 309
.......................................................................................................................................................................................................................................................................................................

output:

14

result:

ok 1 number(s): "14"

Test #31:

score: 0
Accepted
time: 3ms
memory: 4888kb

input:

574 923
.......................................................................................................................................................................................................................................................................................................

output:

47

result:

ok 1 number(s): "47"

Test #32:

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

input:

180 259
...................................................................................................................................................................................................................................................................
...................................

output:

13

result:

ok 1 number(s): "13"

Test #33:

score: 0
Accepted
time: 3ms
memory: 6116kb

input:

169 947
.......................................................................................................................................................................................................................................................................................................

output:

44

result:

ok 1 number(s): "44"

Test #34:

score: 0
Accepted
time: 2ms
memory: 4988kb

input:

892 244
....................................................................................................................................................................................................................................................
..................................................

output:

36

result:

ok 1 number(s): "36"

Test #35:

score: 0
Accepted
time: 4ms
memory: 5056kb

input:

1000 598
......................................................................................................................................................................................................................................................................................................

output:

57

result:

ok 1 number(s): "57"

Test #36:

score: 0
Accepted
time: 4ms
memory: 6904kb

input:

821 608
.......................................................................................................................................................................................................................................................................................................

output:

47

result:

ok 1 number(s): "47"

Test #37:

score: 0
Accepted
time: 3ms
memory: 6128kb

input:

223 988
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #38:

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

input:

141 139
...........................................................................................................................................
...........................................................................................................................................
...............

output:

2

result:

ok 1 number(s): "2"

Test #39:

score: 0
Accepted
time: 5ms
memory: 4992kb

input:

921 940
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #40:

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

input:

317 124
............................................................................................................................
............................................................................................................................
.............................................

output:

14

result:

ok 1 number(s): "14"

Test #41:

score: 0
Accepted
time: 3ms
memory: 6092kb

input:

692 482
.......................................................................................................................................................................................................................................................................................................

output:

38

result:

ok 1 number(s): "38"

Test #42:

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

input:

464 313
.......................................................................................................................................................................................................................................................................................................

output:

25

result:

ok 1 number(s): "25"

Test #43:

score: 0
Accepted
time: 3ms
memory: 6840kb

input:

697 545
.......................................................................................................................................................................................................................................................................................................

output:

35

result:

ok 1 number(s): "35"

Test #44:

score: 0
Accepted
time: 2ms
memory: 6092kb

input:

265 445
.......................................................................................................................................................................................................................................................................................................

output:

19

result:

ok 1 number(s): "19"

Test #45:

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

input:

701 197
.....................................................................................................................................................................................................
.................................................................................................

output:

35

result:

ok 1 number(s): "35"

Test #46:

score: 0
Accepted
time: 3ms
memory: 4888kb

input:

572 761
.......................................................................................................................................................................................................................................................................................................

output:

41

result:

ok 1 number(s): "41"

Test #47:

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

input:

254 236
............................................................................................................................................................................................................................................
..........................................................

output:

9

result:

ok 1 number(s): "9"

Test #48:

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

input:

644 866
.......................................................................................................................................................................................................................................................................................................

output:

46

result:

ok 1 number(s): "46"

Test #49:

score: 0
Accepted
time: 4ms
memory: 6228kb

input:

528 898
.......................................................................................................................................................................................................................................................................................................

output:

44

result:

ok 1 number(s): "44"

Test #50:

score: 0
Accepted
time: 3ms
memory: 5024kb

input:

796 387
.......................................................................................................................................................................................................................................................................................................

output:

34

result:

ok 1 number(s): "34"

Test #51:

score: 0
Accepted
time: 5ms
memory: 6692kb

input:

862 785
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #52:

score: 0
Accepted
time: 4ms
memory: 6488kb

input:

688 663
.......................................................................................................................................................................................................................................................................................................

output:

46

result:

ok 1 number(s): "46"

Test #53:

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

input:

372 589
.......................................................................................................................................................................................................................................................................................................

output:

25

result:

ok 1 number(s): "25"

Test #54:

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

input:

100 1000
......................................................................................................................................................................................................................................................................................................

output:

94

result:

ok 1 number(s): "94"

Test #55:

score: 0
Accepted
time: 2ms
memory: 4924kb

input:

999 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

94

result:

ok 1 number(s): "94"

Test #56:

score: 0
Accepted
time: 4ms
memory: 6916kb

input:

998 1000
......................................................................................................................................................................................................................................................................................................

output:

134

result:

ok 1 number(s): "134"