ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201762 | #3512. 相似 | Daniel1024 | 100 | 32467ms | 64984kb | C++ | 2.7kb | 2024-02-06 10:31:00 | 2024-02-06 13:02:23 |
answer
#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int a[1005][1005];
int p[1005][1005];
int s[1005][1005];
int ord[1005];
int rand(int l, int r){
return 1ll * rand() * rand() % (r - l + 1) + l;
}
map<int, int> mp;
vector<int>t[1000005];
int cnt;
int rnk[1005];
void add(int x, int y, int xx, int yy){
// cout << x << " " << y << " " << xx << " " << yy << endl;
s[xx][yy]++;
s[x - 1][y - 1]++;
s[x - 1][yy]--;
s[xx][y - 1]--;
}
void get(int h){
for(int i = n; i >= 1; i--){
p[h][i] = s[h][i];
s[h - 1][i] += s[h][i];
s[h][i - 1] += s[h][i];
s[h - 1][i - 1] -= s[h][i];
s[h][i] = 0;
}
}
signed main(){
srand(time(0));
cin >> n >> m >> q;
set<int>st;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &a[i][j]);
st.insert(a[i][j]);
}
}
for(set<int>::iterator it = st.begin(); it != st.end(); it++){
int i = *it;
mp[i] = ++cnt;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = mp[a[i][j]];
t[a[i][j]].push_back(i);
}
}
for(int i = 1; i <= n; i++)ord[i] = i;
for(int i = 1; i + 1 <= n; i++){
swap(ord[i], ord[rand(i + 1, n)]);
}
// for(int i = 1; i <= n; i++)cout << ord[i] << " ";
// cout << endl;
for(int i = 1; i <= n; i++)rnk[ord[i]] = i;
bitset<1005>bit;
// cout << "!" << endl;
for(int i = 1; i <= 1000000; i++){
bit.reset();
for(int j = 0; j < t[i].size(); j++){
bit[rnk[t[i][j]]] = 1;
}
vector<pair<int, int> > d;
for(int j = bit._Find_first(); j != bit.size(); j = bit._Find_next(j)){
if(!d.size())d.push_back(make_pair(j, j));
else{
if(bit[j - 1]){
d[d.size() - 1].second++;
}else{
d.push_back(make_pair(j, j));
}
}
}
for(int j = 0; j < d.size(); j++){
for(int k = 0; k < d.size(); k++){
add(d[j].first, d[k].first, d[j].second, d[k].second);
}
}
}
for(int i = n; i >= 1; i--){
get(i);
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++){
// cout << p[i][j] << " ";
// }
// cout << endl;
// }
while(q--){
int x, y;
scanf("%d%d", &x, &y);
x = rnk[x];
y = rnk[y];
int fz = p[x][y];
int fm = m * 2 - p[x][y];
double ans = 1.0 * fz / fm;
printf("%.10lf\n", ans);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 1638ms
memory: 64424kb
input:
1000 1000 50000 782874600 317414125 535524055 470778125 617785930 967513002 334501895 935617907 2349...
output:
0.2399256045 0.0357327809 0.3404825737 0.0101010101 0.0309278351 0.0875475802 0.0598834128 0.0982976...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #2:
score: 5
Accepted
time: 1611ms
memory: 64160kb
input:
1000 1000 50000 322948427 348340642 951901535 882304602 774622595 45176079 681673661 585760805 14415...
output:
0.0080645161 0.1031439603 0.0020040080 0.0828370330 0.0025062657 0.0005002501 0.4398848092 0.3342228...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #3:
score: 5
Accepted
time: 1553ms
memory: 64276kb
input:
1000 1000 50000 413004945 855156301 325682796 769738446 429795888 481834535 978375415 567354766 1176...
output:
0.1142061281 0.2217470984 0.0282776350 0.0193679918 0.0101010101 0.1695906433 0.4044943820 0.4388489...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #4:
score: 5
Accepted
time: 1491ms
memory: 63836kb
input:
1000 1000 50000 786792100 200916537 694788944 879800337 709081207 696703528 454251218 353235184 5223...
output:
0.3333333333 0.0025062657 0.1129660545 0.0055304173 0.4695077149 0.0183299389 0.0025062657 0.0167768...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #5:
score: 5
Accepted
time: 1659ms
memory: 63912kb
input:
1000 1000 50000 851385192 451792384 568949680 158963272 7330315 129569022 489292210 140953897 204806...
output:
0.0040160643 0.0319917441 0.2210012210 0.4695077149 0.2330456227 0.0449320794 0.0020040080 0.0157440...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #6:
score: 5
Accepted
time: 1174ms
memory: 43940kb
input:
1000 1000 500000 13963 12988 15396 16038 4571 1694 6951 6381 6485 131 5128 10147 19263 13681 1485 82...
output:
0.0822510823 0.0005002501 0.0351966874 0.2738853503 0.1947431302 0.0325245225 0.0157440325 0.1778563...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #7:
score: 5
Accepted
time: 1282ms
memory: 43832kb
input:
1000 1000 500000 15491 12415 16064 10638 6543 4649 8903 8283 9492 11826 18467 75 18625 5972 6117 561...
output:
0.0095911156 0.1123470523 0.0045203415 0.0015022534 0.1273957159 0.0000000000 0.0576414595 0.0106114...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #8:
score: 5
Accepted
time: 1288ms
memory: 43940kb
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.0515247108 0.0251153255 0.0400416017 0.3679890561 0.0230179028 0.1587485...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #9:
score: 5
Accepted
time: 1201ms
memory: 43976kb
input:
1000 1000 500000 17515 1654 6128 8954 10419 15429 12822 3633 571 13976 11315 13703 9770 18046 13951 ...
output:
0.2437810945 0.3879250520 0.0482180294 0.0000000000 0.5432098765 0.0005002501 0.1813349084 0.3956734...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #10:
score: 5
Accepted
time: 1228ms
memory: 43936kb
input:
1000 1000 500000 3678 10238 2800 6025 19030 7706 16755 281 15620 11849 1560 3972 5223 15072 12467 15...
output:
0.1086474501 0.1862396204 0.4255167498 0.5278838808 0.0746910263 0.0080645161 0.2121212121 0.3976240...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #11:
score: 5
Accepted
time: 1812ms
memory: 64156kb
input:
1000 1000 500000 530309921 764142048 340489916 874774180 653462377 303787798 226672031 860744458 814...
output:
0.0147133435 0.0080645161 0.0548523207 0.0718113612 0.0454783063 0.0869565217 0.0816657653 0.0020040...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #12:
score: 5
Accepted
time: 1878ms
memory: 64984kb
input:
1000 1000 500000 136111449 972776136 121949178 118026305 879638749 702193817 878860889 902233549 320...
output:
0.0834236186 0.1344299490 0.0030090271 0.0020040080 0.0723860590 0.3614703880 0.0010010010 0.2232415...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #13:
score: 5
Accepted
time: 1826ms
memory: 64948kb
input:
1000 1000 500000 702535687 245896643 156765366 732302099 444697307 729791887 237943212 594396381 850...
output:
0.1890606421 0.2368583797 0.4104372355 0.0035122930 0.0542962572 0.0000000000 0.0905125409 0.2666244...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #14:
score: 5
Accepted
time: 1804ms
memory: 64156kb
input:
1000 1000 500000 215144314 343298002 152190218 99925872 89639480 630079250 130912459 97182795 449494...
output:
0.0060362173 0.0157440325 0.0542962572 0.1933174224 0.0214504597 0.0045203415 0.1280315849 0.1961722...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #15:
score: 5
Accepted
time: 1752ms
memory: 64564kb
input:
1000 1000 500000 909687812 646480383 242336193 363071594 880929203 536737767 742318012 488460271 769...
output:
0.0000000000 0.0005002501 0.0615711253 0.0111223458 0.0000000000 0.0487676980 0.0325245225 0.0000000...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #16:
score: 5
Accepted
time: 1781ms
memory: 64664kb
input:
1000 1000 500000 769054130 847792936 591861562 834565671 936011861 632186281 415150954 119413997 466...
output:
0.3586956522 0.0282776350 0.4450867052 0.0111223458 0.0025062657 0.1682242991 0.0934937124 0.3531799...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #17:
score: 5
Accepted
time: 1846ms
memory: 64660kb
input:
1000 1000 500000 405394009 776039949 191855784 209113942 740893905 206932230 583774856 675007232 682...
output:
0.1947431302 0.0610079576 0.2165450122 0.0005002501 0.3486176669 0.0863661054 0.0065425264 0.4903129...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #18:
score: 5
Accepted
time: 1846ms
memory: 64036kb
input:
1000 1000 500000 736680326 686840638 915216082 724177007 986075963 662542469 67387388 101765943 2816...
output:
0.4461315980 0.3966480447 0.0000000000 0.0224948875 0.0172939980 0.1567379988 0.0465724751 0.2618296...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #19:
score: 5
Accepted
time: 1954ms
memory: 64140kb
input:
1000 1000 500000 318410081 501282253 99615288 861382903 784680221 23862891 711357980 777119106 23373...
output:
0.1013215859 0.4275517488 0.1976047904 0.0121457490 0.0065425264 0.5420200463 0.0204081633 0.0055304...
result:
ok ALL ANSWERS ARE CORRECT!!!
Test #20:
score: 5
Accepted
time: 1843ms
memory: 63632kb
input:
1000 1000 500000 510909337 322206127 744281416 223170461 789405384 578715675 880024238 833958902 606...
output:
0.0141987830 0.5003750938 0.0598834128 0.0193679918 0.3149243918 0.0000000000 0.2437810945 0.1448196...
result:
ok ALL ANSWERS ARE CORRECT!!!