QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #276718 | #6357. 排序 | SoyTony | 0 | 0ms | 0kb | C++14 | 1.5kb | 2023-12-06 10:02:44 | 2023-12-06 10:02:44 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int mod=1e9+7;
const ull bs=233;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int t,n,ans;
struct node{
int x,y;
}a[maxn];
ull h1[maxn<<2],h2[maxn<<2],pw[maxn<<2];
int s[maxn<<2];
int main(){
pw[0]=1;
for(int i=1;i<=400000;++i) pw[i]=pw[i-1]*bs;
t=read();
while(t--){
n=read();
ans=0;
for(int i=1;i<=n;++i){
a[i].x=read(),a[i].y=read();
}
for(int i=1;i<=n;++i){
int p1=i-1,p2=i,p3=i+1;
if(p1<1) p1+=n;
if(p3>n) p3-=n;
//i-1,i
s[i*2-1]=(a[p1].x-a[p2].x)*(a[p1].x-a[p2].x)+(a[p1].y-a[p2].y)*(a[p1].y-a[p2].y);
//i
s[i*2]=(a[p1].x-a[p2].x)*(a[p2].y-a[p3].y)-(a[p1].y-a[p2].y)*(a[p2].x-a[p3].x);
//printf("%d %d %d\n",i,s[i*2-1],s[i*2]);
}
for(int i=1;i<=2*n;++i) s[i+2*n]=s[i];
for(int i=1;i<=4*n;++i) h1[i]=h1[i-1]*bs+s[i];
for(int i=4*n;i>=1;--i) h2[i]=h2[i+1]*bs+s[i];
for(int i=1;i<=2*n;++i){
int l=i,r=i+2*n;
ull hash1=h1[r]-h1[l-1]*pw[r-l+1];
ull hash2=h2[l]-h2[r+1]*pw[r-l+1];
if(hash1==hash2) ++ans;
}
printf("%d\n",ans/2);
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
100 100 46 2 24 25 18 43 19 38 9 6 7 30 16 33 32 47 22 1 14 5 45 23 50 48 40 3 26 21 20 39 29 34 42 17 11 4 12 31 49 8 28 10 44 36 35 37 13 15 41 27 95 55 76 84 63 70 83 89 94 65 100 54 69 86 53 71 57 77 68 81 58 56 64 51 88 74 79 82 52 61 73 96 92 72 78 97 66 60 87 90 93 98 80 91 99 75 85 67 59 62 ...
output:
result:
Test #2:
score: 0
Time Limit Exceeded
input:
100 100 3 28 34 50 2 31 11 23 21 5 13 24 20 39 12 8 46 37 49 6 43 19 42 33 17 4 45 40 47 18 15 35 38 44 7 26 30 9 14 32 25 22 29 1 10 16 36 41 48 27 88 66 59 94 95 99 69 81 79 90 60 86 76 61 85 56 54 82 63 80 75 83 64 97 72 71 52 87 100 55 84 78 62 68 77 89 93 92 58 96 73 91 53 67 65 51 57 74 70 98 ...
output:
result:
Test #3:
score: 0
Time Limit Exceeded
input:
100 100 20 2 1 44 39 15 23 37 25 33 13 14 16 42 26 35 12 32 5 19 11 4 45 24 30 3 27 41 7 10 9 31 48 28 6 21 18 17 8 22 43 29 50 38 36 49 47 40 34 46 55 53 66 72 98 51 71 74 62 54 81 69 91 84 52 65 76 87 94 61 80 99 83 88 63 97 100 75 85 82 92 86 64 67 70 60 56 57 77 58 79 89 90 78 96 68 73 59 93 95 ...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
8050 22018 1 29 31 10 16 46 42 23 44 15 37 17 26 28 48 18 9 39 12 2 41 38 25 5 33 20 34 35 7 6 8 32 4 40 49 3 21 13 50 45 19 27 14 11 24 36 30 43 47 22 69 84 88 100 72 76 95 65 99 87 77 83 70 73 97 67 58 62 71 86 80 57 82 63 91 90 96 85 52 59 94 64 51 60 56 55 74 93 75 68 79 98 81 61 53 66 54 78 92 ...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
1400 31558 11 16 45 42 41 50 10 47 24 38 13 27 43 46 22 39 23 29 32 33 49 25 21 28 14 4 34 8 17 36 48 6 1 35 12 30 44 19 2 40 5 15 18 7 9 26 3 20 31 37 67 57 94 76 66 88 85 86 54 89 79 80 63 74 75 69 78 96 87 91 97 95 61 73 55 62 64 65 92 93 59 99 52 71 53 70 60 100 84 68 58 77 56 90 83 51 72 82 98 ...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
1650 7019 9 15 16 46 19 44 13 11 50 37 5 7 23 36 42 30 34 1 28 45 38 31 21 40 8 24 43 6 48 14 22 39 47 2 29 27 17 35 4 3 10 41 20 12 25 26 49 33 18 32 70 99 74 89 51 82 97 60 88 63 61 90 52 94 57 75 81 76 85 65 91 86 59 66 72 56 93 96 71 79 73 54 98 64 69 83 68 62 53 78 95 55 100 87 80 67 77 92 58 8...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
8700 23581 7 42 44 23 38 25 50 37 20 18 21 3 34 19 11 22 12 17 40 4 30 15 39 28 13 27 1 32 31 24 49 45 33 5 26 43 16 14 2 46 48 10 36 29 8 35 41 9 6 47 92 78 88 66 93 61 63 60 98 64 75 82 59 52 97 70 79 56 90 81 94 57 67 80 100 89 55 99 68 95 86 76 91 62 54 53 83 69 85 72 77 84 96 58 65 73 87 74 71 ...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
9150 13084 9 20 10 44 3 36 1 11 19 23 17 14 27 12 25 2 15 21 26 39 29 22 28 49 16 24 37 7 4 13 50 33 8 31 32 47 42 18 6 5 48 45 46 30 38 41 43 40 35 34 82 51 95 75 73 89 99 63 100 96 61 70 57 93 84 59 87 94 60 85 56 88 81 76 66 64 83 53 71 72 78 67 80 55 74 91 69 68 54 90 98 65 58 86 77 79 92 62 97 ...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100000 100000 9 23 49 19 16 15 1 46 48 11 33 5 21 31 4 43 26 20 13 22 42 10 38 8 34 37 45 7 36 24 6 39 3 18 2 27 44 40 17 50 32 35 29 12 28 25 47 41 30 14 65 87 53 69 86 72 77 63 99 100 75 84 81 95 91 89 80 96 73 52 83 60 66 94 71 59 62 56 92 58 55 68 51 70 90 93 64 74 97 82 88 79 54 76 78 67 98 61 ...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
100000 100000 21 28 36 2 16 48 19 37 7 5 44 30 22 45 3 15 8 9 20 38 12 50 1 43 25 11 4 14 46 13 42 39 10 49 35 17 26 33 23 27 6 18 34 41 29 47 24 31 32 40 93 69 70 91 61 94 87 58 92 73 86 96 64 84 52 98 77 71 53 55 62 75 56 59 68 67 88 83 78 100 54 95 74 97 65 60 80 85 66 72 79 90 76 82 57 51 99 63 ...