結果

問題 No.11 カードマッチ
ユーザー ryo ryoryo ryo
提出日時 2023-08-17 20:26:15
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 180 ms / 5,000 ms
コード長 1,913 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 30,720 KB
実行使用メモリ 103,468 KB
最終ジャッジ日時 2024-05-05 03:20:46
合計ジャッジ時間 2,308 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
25,344 KB
testcase_01 AC 7 ms
25,344 KB
testcase_02 AC 7 ms
25,344 KB
testcase_03 AC 6 ms
25,472 KB
testcase_04 AC 57 ms
58,496 KB
testcase_05 AC 7 ms
25,344 KB
testcase_06 AC 179 ms
103,424 KB
testcase_07 AC 87 ms
51,696 KB
testcase_08 AC 103 ms
65,664 KB
testcase_09 AC 180 ms
103,468 KB
testcase_10 AC 125 ms
88,436 KB
testcase_11 AC 136 ms
81,812 KB
testcase_12 AC 138 ms
84,476 KB
testcase_13 AC 132 ms
79,956 KB
testcase_14 AC 62 ms
55,056 KB
testcase_15 AC 8 ms
25,600 KB
testcase_16 AC 17 ms
28,160 KB
testcase_17 AC 18 ms
28,416 KB
testcase_18 AC 16 ms
28,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

int sort(const void *A,const void *B){
    const int *a=A,*b=B;
    return *a-*b;
}

int main(){
    
    int w,h,n;
    int *g1[1000002];
    int *g2[1000002];
    
    int dg1[1000002]={},dg2[1000002]={};
    int cnt1[1000002]={},cnt2[1000002]={};
    int s[102],k[102];
    scanf("%d%d%d",&w,&h,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&s[i],&k[i]);
        s[i]--; k[i]--;
        dg1[s[i]]++; dg2[k[i]]++;
    }
    
    for(int i=0;i<w;i++)g1[i]=malloc(sizeof(int)*dg1[i]);
    for(int i=0;i<h;i++)g2[i]=malloc(sizeof(int)*dg2[i]);
    
    for(int i=0;i<n;i++){
        g1[s[i]][cnt1[s[i]]]=k[i];
        g2[k[i]][cnt2[k[i]]]=s[i];
        cnt1[s[i]]++; cnt2[k[i]]++;
    }
    
    for(int i=0;i<w;i++)qsort(g1[i],dg1[i],sizeof(int),sort);
    for(int i=0;i<h;i++)qsort(g2[i],dg2[i],sizeof(int),sort);
    
 /*   for(int i=0;i<w;i++){
        for(int j=0;j<dg1[i];j++)printf("%d ",1+g1[i][j]);
        printf("\n");
    }
 */ 
   // for(int i=0;i<h;i++)printf("[%d]",dg2[i]);
    
    int seen1[1000002]={},seen2[1000002]={};
    int ans=0;
    
     for(int i=0;i<n;i++){
        int x=s[i];
        
        if(seen2[x]==0){
            seen2[x]=1;
            int p=dg1[x];
            int t=0;
            
            
            
            for(int j=0;j<h;j++){ 
                if(j==g1[x][t]){
                    t++; continue; 
                }
            //    printf("{%d}",j);
                
                dg2[j]++;
            }
            ans+=h-p;
        //    printf("[%d:%d]\n",i,h-p);
        }
    }
    
   // for(int i=0;i<h;i++)printf("%d ",dg2[i]);
   
    for(int i=0;i<n;i++){
       
        int y=k[i];
        if(seen1[y]==0){
            seen1[y]=1;
            int p=dg2[y];
            
            ans+=w-p; 
            //printf("[%d:%d]\n",i,w-p);
        }
    }
    
   
    printf("%d",ans);
    return 0;
}
0