Submission #2150954


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,belong;
  SCC(){}
  SCC(int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
  
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
  
  void input(int m,int offset=0){
    int a,b;
    for(int i=0;i<m;i++){
      cin>>a>>b;
      add_edge(a+offset,b+offset);
    }
  }
  
  void dfs(int v){
    used[v]=1;
    for(int i=0;i<(int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
  
  void rdfs(int v,int k){
    used[v]=1;
    belong[v]=k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++){
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
  
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
	T.push_back(vector<int>());
	C.push_back(vector<int>());
	rdfs(vs[i],k++);
      }
    }
    for(int i=0;i<n;i++)
      for(int u:G[i])
	if(belong[i]!=belong[u])
	  T[belong[i]].push_back(belong[u]);
    for(int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }
};


int diff(int a, int b){//time difference
  int ret=abs(a-b);
  return min(ret, 24-ret);
}

int main(void) {
  int i,j;
  int n;
  cin>>n;

  vi a(n);
  rep(i,n)cin>>a[i];
  a.push_back(0);
  n++;

  for(int ans=12;ans>=0;ans--){

    SCC scc((n+1)*2);//1-indexed

    rep(i,n) rep(j,n){
      if(i==j) continue;
      if(diff(a[i], a[j]) < ans){
	scc.add_edge(n+(i+1), n-(j+1));
	scc.add_edge(n-(i+1), n+(j+1));
      }
      if(diff(a[i], 24-a[j]) < ans){
	scc.add_edge(n-(i+1), n-(j+1));
	scc.add_edge(n+(i+1), n+(j+1));
      }

    }

    scc.build();

    bool c=true;

    auto belong=scc.belong;
    for(int i=0;i<n;i++){
      if(belong[n-(i+1)]==belong[n+(i+1)]){
	c=false;
      }
    }
    if(c){
      cout<<ans<<endl;
      return 0;
    }

  }

}

Submission Info

Submission Time
Task C - Time Gap
User rika0384
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2854 Byte
Status
Exec Time 3 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 500 / 500 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt 1 ms 256 KB
01-02.txt 1 ms 256 KB
01-03.txt 1 ms 256 KB
01-04.txt 1 ms 256 KB
01-05.txt 1 ms 256 KB
01-06.txt 1 ms 256 KB
01-07.txt 1 ms 256 KB
01-08.txt 1 ms 256 KB
01-09.txt 1 ms 256 KB
01-10.txt 1 ms 256 KB
01-11.txt 1 ms 256 KB
01-12.txt 1 ms 256 KB
01-13.txt 1 ms 256 KB
01-14.txt 2 ms 256 KB
01-15.txt 2 ms 256 KB
01-16.txt 3 ms 384 KB
01-17.txt 1 ms 256 KB
01-18.txt 1 ms 256 KB
01-19.txt 1 ms 256 KB
01-20.txt 1 ms 256 KB
01-21.txt 1 ms 256 KB
01-22.txt 1 ms 256 KB
01-23.txt 1 ms 256 KB
01-24.txt 1 ms 256 KB
01-25.txt 1 ms 256 KB
01-26.txt 1 ms 256 KB
01-27.txt 1 ms 256 KB
01-28.txt 1 ms 256 KB
01-29.txt 1 ms 256 KB
01-30.txt 1 ms 256 KB
01-31.txt 1 ms 256 KB
01-32.txt 1 ms 256 KB
01-33.txt 1 ms 256 KB
01-34.txt 1 ms 256 KB
01-35.txt 1 ms 256 KB
01-36.txt 1 ms 256 KB
01-37.txt 1 ms 256 KB
01-38.txt 1 ms 256 KB
01-39.txt 2 ms 256 KB
01-40.txt 2 ms 256 KB
01-41.txt 1 ms 256 KB
01-42.txt 3 ms 384 KB
01-43.txt 1 ms 256 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB