UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201780#3512. 相似Daniel102410017541ms49588kbC++3.5kb2024-02-06 11:35:112024-02-06 13:07:44

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;
}
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;
    }
}
int o[1000005], tot;
int read(){
    int s = 0;
    char ch = getchar();
    while('0' > ch || ch > '9')ch = getchar();
    while('0' <= ch && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s;
}
signed main(){
    // freopen("similarity2.in", "r", stdin);
    // freopen("my.out", "w", stdout);
    srand(time(0));
    // double stt = clock();
    cin >> n >> m >> q;
    vector<int>r;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            a[i][j] = read();
            o[++tot] = a[i][j];
        }
    }
    sort(o + 1, o + 1 + tot);
    int len = 0;
    for(int i = 1; i <= tot; i++){
        if(i == 1 || o[i] != o[i - 1])o[++len] = o[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int l = 1, r = len;
            while(l <= r){
                int mid = l+r>>1;
                if(a[i][j] < o[mid]){
                    r = mid - 1;
                }else if(a[i][j] > o[mid]){
                    l = mid + 1;
                }else{
                    a[i][j] = mid;
                    break;
                }
            }
            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;
        x = read();
        y = read();
        x = rnk[x];
        y = rnk[y];
        if(x == y)p[x][y] = m;
        int fz = p[x][y];
        int fm = m * 2 - p[x][y];
        double ans = 1.0 * fz / fm;
        printf("%.10lf\n", ans);
    }
    // cerr << "MY:" << (double)(clock()) - stt << endl;
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 732ms
memory: 49524kb

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: 699ms
memory: 49388kb

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: 742ms
memory: 49516kb

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: 718ms
memory: 49468kb

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: 684ms
memory: 49448kb

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: 845ms
memory: 46388kb

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: 976ms
memory: 46404kb

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: 951ms
memory: 46376kb

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: 869ms
memory: 46208kb

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: 873ms
memory: 46204kb

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: 915ms
memory: 49376kb

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: 904ms
memory: 49588kb

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: 1024ms
memory: 49552kb

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: 978ms
memory: 49516kb

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: 948ms
memory: 49528kb

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: 934ms
memory: 49544kb

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: 879ms
memory: 49520kb

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: 989ms
memory: 49452kb

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: 938ms
memory: 49376kb

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: 943ms
memory: 49376kb

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!!!