글 읽기 - 시간초과가 뜹니다.

impri 4년 전 0

포함 배제 원리와 이진 탐색으로 풀었는데 시간 초과가 뜹니다. 뭐가 문제일까요?

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
vector<vector<int> >arr;
vector<int> cows[50001];


int main()
{ cin.tie(0);
 ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=5;j++){
        int a;
        cin >> a;
        cows[i].push_back(a);
    }
    sort(cows[i].begin(),cows[i].end());

  }

  for(int i=1;i<=n;i++){

    for(int j=31;j>0;j--){
              vector<int>temp;
   
        for(int k=0;k<5;k++){
            if(j & (1 << k)){
                temp.push_back(cows[i][k]);
            }
        }
        arr.push_back(temp);
    }

  }

    sort(arr.begin(),arr.end());
  long long res=0;

  for(int i=1;i<=n;i++){

     long long t=0;
     for(int j=31;j>0;j--){
              vector<int>temp ;
        for(int k=0;k<5;k++){
            if(j & (1 << k)){
                temp.push_back(cows[i][k]);
            }
        }
       int cnt=upper_bound(arr.begin(),arr.end(),temp)-lower_bound(arr.begin(),arr.end(),temp);
       if(temp.size()%2==0)t-=1LL*cnt;
       else t+=1LL*cnt;

    }
    res+=(n-t);

  }
  cout << res/2;


}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 뜹니다.

impri 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말