CODE FESTIVAL 2016 Exhibition(Parallel)

Submission #1053891

Source codeソースコード

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int n;
pair<int,int> a[maxn];

bool check_1(){
  if(a[1].first!=0||a[2].second!=0||a[2].first!=a[1].second)return false;
  for(int i=3;i<=n;i++)
    if(a[i].first==0||a[i].second==0)return false;
  set<pair<int,int>>st;
  for(int i=1;i<=n;i++)st.insert(a[i]);
  for(int i=3;i<=n;i++){
    int cnt=0;
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first-1,a[i].second+j))!=st.end()){
        cnt++;
        break;
      }
    for(int j=-1;j<=1;j++)
      if(st.find(make_pair(a[i].first+j,a[i].second-1))!=st.end()){
        cnt++;
        break;
      }
      if(cnt<2)return false;
  }
  return true;
}

bool cmp(pair<int,int> a,pair<int,int> b){
  int ta = a.first + a.second;
  int tb = b.first + b.second;
  return ta == tb ? a.first < b.first: ta < tb;
}

int cal(){
  int ret=0;
  sort(a+1,a+n+1,cmp);
  map<pair<int,int>,int>mp;
  map<pair<int,int>,int>f[2];
  for(int i=1;i<=n;i++){
    int pos = i;
    vector<pair<int,int>>v;
    v.push_back(a[i]);
    for(int j = i;j<=n;j++){
      if(a[j].first + a[j].second!=a[i].first + a[i].second)break;
      pos = j;
      if(mp.find(a[j])==mp.end())mp[a[j]]=1;
      else mp[a[j]]+=1;
      f[0][a[j]] = f[1][a[j]] = -1;
      if(j>i&&a[j]!=a[i])v.push_back(a[j]);
    }
    f[0][v[0]]=0;
    if(mp.find(make_pair(v[0].first-1,v[0].second-1))!=mp.end()){
      f[1][v[0]] = mp[v[0]];
    }
    for(int j=0;j+1<v.size();j++){
      if(f[0][v[j]]!=-1){
        if(v[j].first == v[j+1].first - 1){
          f[0][v[j+1]] = max(f[0][v[j+1]],f[0][v[j]] + min(mp[v[j]],mp[v[j+1]]));
        } else {
          f[0][v[j+1]] = max(f[0][v[j+1]],f[0][v[j]]);
        }
        if(mp.find(make_pair(v[j+1].first-1,v[j+1].second-1))!=mp.end()){
          f[1][v[j+1]] = max(f[1][v[j+1]],f[0][v[j]]+mp[v[j+1]]);
        }
      }
      if(f[1][v[j]]!=-1){
        f[0][v[j+1]] = max(f[0][v[j+1]],f[1][v[j]]);
        if(mp.find(make_pair(v[j+1].first-1,v[j+1].second-1))!=mp.end()){
          f[1][v[j+1]] = max(f[1][v[j+1]],f[1][v[j]]+mp[v[j+1]]);
        }
      }
    }
    ret += max(0, max(f[0][v[v.size()-1]],f[1][v[v.size()-1]]));
    i =pos;
  }
  return ret;
}

int main() {
//    freopen("in.cpp","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int x,y;
        cin>>x>>y;
        a[i].first = x;
        a[i].second = y;
    }
    if(!check_1()){
      cout<<-1<<endl;
      return 0;
    }
    cout<<2*n-2-cal()<<endl;
    return 0;
}

Submission

Task問題 A - Distance Pairs
User nameユーザ名 suiyuan2009
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2775 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
All 0 / 1500 sample-01.txt,sample-02.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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 92 ms 5760 KB
01-02.txt AC 39 ms 1024 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt WA
01-06.txt WA
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
01-11.txt WA
01-12.txt WA
01-13.txt AC 397 ms 19712 KB
01-14.txt AC 363 ms 20604 KB
01-15.txt AC 365 ms 19712 KB
01-16.txt AC 43 ms 1024 KB
01-17.txt AC 50 ms 2168 KB
01-18.txt AC 44 ms 1024 KB
01-19.txt AC 369 ms 19964 KB
01-20.txt WA
01-21.txt WA
01-22.txt WA
01-23.txt AC 58 ms 1280 KB
01-24.txt AC 64 ms 1280 KB
01-25.txt AC 40 ms 1024 KB
01-26.txt AC 40 ms 1024 KB
01-27.txt AC 39 ms 1024 KB
01-28.txt AC 42 ms 1024 KB
01-29.txt WA
01-30.txt AC 3 ms 256 KB
01-31.txt AC 3 ms 256 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB