ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201768 | #3512. 相似 | Little09 | 100 | 15470ms | 46780kb | C++11 | 1.8kb | 2024-02-06 11:03:31 | 2024-02-06 13:03:34 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937 rnd(time(0));
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}
const ll inf=1000000000000000000;
//const ll inf=1000000000;
//const ll mod=998244353;
//const ll mod=1000000007;
const int N=1005;
double alpha=0.5;
int n,m,q,cnt,B;
int a[N][N],ans[N][N],top[N*N];
int c[N*N];
vector<int>b[N*N];
int id[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
rep(i,1,n) rep(j,1,m) cin >> a[i][j];
rep(i,1,n) rep(j,1,m) c[++cnt]=a[i][j];
sort(c+1,c+cnt+1);
cnt=unique(c+1,c+cnt+1)-c-1;
rep(i,1,n) rep(j,1,m) a[i][j]=lower_bound(c+1,c+cnt+1,a[i][j])-c,b[a[i][j]].pb(i);
B=m*alpha;
if (B<=10) B=m;
alpha=1.0*B/m;
rep(i,1,n)
{
rep(j,1,m) id[j]=j;
shuffle(id+1,id+m+1,rnd);
rep(j,1,B)
{
int col=a[i][id[j]],len=SZ(b[col]);
rep(k,top[col],len-1) ans[i][b[col][k]]++;
}
rep(j,1,m) top[a[i][j]]++;
}
rep(i,1,q)
{
int x,y;
cin >> x >> y;
if (x>y) swap(x,y);
if (x==y) cout << "1\n";
else
{
double r=2*m-ans[x][y]/alpha;
double res=2.0*m/r-1;
cout << fixed << setprecision(10) << res << endl;
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 622ms
memory: 46548kb
input:
1000 1000 50000 782874600 317414125 535524055 470778125 617785930 967513002 334501895 935617907 2349...
output:
0.2500000000 0.0351966874 0.3351134846 0.0121457490 0.0298661174 0.0928961749 0.0626992561 0.1037527...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #2:
score: 5
Accepted
time: 568ms
memory: 46540kb
input:
1000 1000 50000 322948427 348340642 951901535 882304602 774622595 45176079 681673661 585760805 14415...
output:
0.0090817356 0.1049723757 0.0010010010 0.0917030568 0.0040160643 0.0010010010 0.4245014245 0.3054830...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #3:
score: 5
Accepted
time: 609ms
memory: 46572kb
input:
1000 1000 50000 413004945 855156301 325682796 769738446 429795888 481834535 978375415 567354766 1176...
output:
0.0893246187 0.2048192771 0.0256410256 0.0172939980 0.0101010101 0.1764705882 0.4164305949 0.4224751...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #4:
score: 5
Accepted
time: 580ms
memory: 46596kb
input:
1000 1000 50000 786792100 200916537 694788944 879800337 709081207 696703528 454251218 353235184 5223...
output:
0.3333333333 0.0020040080 0.1123470523 0.0040160643 0.4836795252 0.0152284264 0.0010010010 0.0172939...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #5:
score: 5
Accepted
time: 558ms
memory: 46580kb
input:
1000 1000 50000 851385192 451792384 568949680 158963272 7330315 129569022 489292210 140953897 204806...
output:
0.0030090271 0.0362694301 0.2239902081 0.4409221902 0.2360939431 0.0460251046 0.0010010010 0.0152284...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #6:
score: 5
Accepted
time: 730ms
memory: 42808kb
input:
1000 1000 500000 13963 12988 15396 16038 4571 1694 6951 6381 6485 131 5128 10147 19263 13681 1485 82...
output:
0.0764262648 0.0010010010 0.0373443983 0.2674271229 0.1876484561 0.0319917441 0.0121457490 0.1918951...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #7:
score: 5
Accepted
time: 716ms
memory: 42828kb
input:
1000 1000 500000 15491 12415 16064 10638 6543 4649 8903 8283 9492 11826 18467 75 18625 5972 6117 561...
output:
0.0090817356 0.1135857461 0.0060362173 0.0000000000 0.1235955056 0.0000000000 0.0548523207 0.0121457...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #8:
score: 5
Accepted
time: 672ms
memory: 42796kb
input:
1000 1000 500000 17554 1410 7352 16882 12949 2339 1427 15585 7723 7840 18829 5926 8512 16593 2502 17...
output:
0.0000000000 0.0000000000 0.0460251046 0.0277492292 0.0427528676 0.3755158184 0.0245901639 0.1560693...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #9:
score: 5
Accepted
time: 707ms
memory: 42712kb
input:
1000 1000 500000 17515 1654 6128 8954 10419 15429 12822 3633 571 13976 11315 13703 9770 18046 13951 ...
output:
0.2254901961 0.3869625520 0.0515247108 0.0000000000 0.5432098765 0.0000000000 0.1750881316 0.3966480...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #10:
score: 5
Accepted
time: 725ms
memory: 42712kb
input:
1000 1000 500000 3678 10238 2800 6025 19030 7706 16755 281 15620 11849 1560 3972 5223 15072 12467 15...
output:
0.1160714286 0.1627906977 0.4245014245 0.5313935681 0.0706638116 0.0060362173 0.2150668287 0.3947001...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #11:
score: 5
Accepted
time: 852ms
memory: 46528kb
input:
1000 1000 500000 530309921 764142048 340489916 874774180 653462377 303787798 226672031 860744458 814...
output:
0.0162601626 0.0090817356 0.0537407798 0.0695187166 0.0427528676 0.0905125409 0.0822510823 0.0030090...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #12:
score: 5
Accepted
time: 890ms
memory: 46772kb
input:
1000 1000 500000 136111449 972776136 121949178 118026305 879638749 702193817 878860889 902233549 320...
output:
0.0917030568 0.1325028313 0.0020040080 0.0010010010 0.0741138561 0.3774104683 0.0000000000 0.2135922...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #13:
score: 5
Accepted
time: 905ms
memory: 46780kb
input:
1000 1000 500000 702535687 245896643 156765366 732302099 444697307 729791887 237943212 594396381 850...
output:
0.1848341232 0.2135922330 0.4144271570 0.0040160643 0.0593220339 0.0000000000 0.0928961749 0.2771392...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #14:
score: 5
Accepted
time: 885ms
memory: 46556kb
input:
1000 1000 500000 215144314 343298002 152190218 99925872 89639480 630079250 130912459 97182795 449494...
output:
0.0040160643 0.0162601626 0.0537407798 0.2077294686 0.0204081633 0.0070493454 0.1402508552 0.1904761...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #15:
score: 5
Accepted
time: 888ms
memory: 46652kb
input:
1000 1000 500000 909687812 646480383 242336193 363071594 880929203 536737767 742318012 488460271 769...
output:
0.0000000000 0.0000000000 0.0582010582 0.0090817356 0.0000000000 0.0526315789 0.0351966874 0.0000000...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #16:
score: 5
Accepted
time: 932ms
memory: 46704kb
input:
1000 1000 500000 769054130 847792936 591861562 834565671 936011861 632186281 415150954 119413997 466...
output:
0.3679890561 0.0214504597 0.4409221902 0.0121457490 0.0030090271 0.1709601874 0.0729613734 0.3422818...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #17:
score: 5
Accepted
time: 875ms
memory: 46680kb
input:
1000 1000 500000 405394009 776039949 191855784 209113942 740893905 206932230 583774856 675007232 682...
output:
0.1723329426 0.0649627263 0.2165450122 0.0000000000 0.3280212483 0.0787486516 0.0080645161 0.4792899...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #18:
score: 5
Accepted
time: 892ms
memory: 46592kb
input:
1000 1000 500000 736680326 686840638 915216082 724177007 986075963 662542469 67387388 101765943 2816...
output:
0.4577259475 0.4084507042 0.0000000000 0.0214504597 0.0152284264 0.1600928074 0.0460251046 0.2468827...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #19:
score: 5
Accepted
time: 1002ms
memory: 46560kb
input:
1000 1000 500000 318410081 501282253 99615288 861382903 784680221 23862891 711357980 777119106 23373...
output:
0.1198208287 0.4204545455 0.2019230769 0.0111223458 0.0070493454 0.5625000000 0.0162601626 0.0060362...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #20:
score: 5
Accepted
time: 862ms
memory: 46492kb
input:
1000 1000 500000 510909337 322206127 744281416 223170461 789405384 578715675 880024238 833958902 606...
output:
0.0141987830 0.4925373134 0.0537407798 0.0235414534 0.3192612137 0.0000000000 0.2360939431 0.1376564...
result:
ok ALL ANSWERS ARE CORRECT!!!