QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#566033 | #7725. Just Sum Two Numbers | Crysfly | AC ✓ | 6ms | 7192kb | C++14 | 4.5kb | 2024-09-15 22:54:59 | 2024-09-15 22:55:00 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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"