結果

問題 No.11 カードマッチ
コンテスト
ユーザー ryo ryo
提出日時 2023-08-17 20:26:15
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 201 ms / 5,000 ms
コード長 1,913 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 30,848 KB
実行使用メモリ 103,424 KB
最終ジャッジ日時 2024-11-26 20:40:38
合計ジャッジ時間 3,259 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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