結果

問題 No.466 ジオラマ
ユーザー chaemon
提出日時 2016-12-16 01:13:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,405 bytes
コンパイル時間 1,473 ms
コンパイル使用メモリ 111,192 KB
実行使用メモリ 10,016 KB
最終ジャッジ日時 2024-10-15 01:01:08
合計ジャッジ時間 13,883 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 3
other AC * 34 RE * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'bool check(int, const std::vector<std::pair<int, int> >&)':
main.cpp:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

// #includes {{{
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <cmath>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair
#define EXIST(e,s) ((s).find(e)!=(s).end())
#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;
const int INF=0x3f3f3f3f;
typedef long long Int;
typedef unsigned long long uInt;
#ifdef __MINGW32__
typedef double rn;
#else
typedef long double rn;
#endif
typedef pair<int,int> pii;
/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}
int vis[1001000];
//{{{ Graph
typedef int Weight;
struct Edge {
    int src, dst, rev;
    Weight weight;
    Edge(int src, int dst, Weight weight=1,int rev=-1) :
        src(src), dst(dst), weight(weight), rev(rev) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
//add bi-directional edge
void addBiEdge(Graph &g,int from ,int to, Weight w=1){
    while(g.size()<max(from,to)+1)g.push_back(Edges());
    g[from].push_back(Edge(from,to,w,g[to].size()));
    g[to].push_back(Edge(to,from,w,g[from].size()-1));
}
//add directional edge
void addEdge(Graph &g,int from ,int to, Weight w=1){
    while(g.size()<from+1)g.push_back(Edges());
    g[from].push_back(Edge(from,to,w));
}
#ifdef DEBUG
#include"graph/graphviz.h"
#endif
//}}}
Graph g;
void dfs(int u,int b){
    if(vis[u]&b)return;
    vis[u]|=b;
    FOR(e,g[u]){
        dfs(e->dst,b);
    }
}
int A,B,C,D;
bool check(int N,const vector<pii> &e){
    g.assign(N,Edges());
    REP(i,e.size())g[e[i].first].push_back(Edge(e[i].first,e[i].second));
    set<pii> s;
    REP(i,e.size()){
        assert(e[i].first!=e[i].second);
        assert(0<=e[i].first and e[i].first<N and 0<=e[i].second and e[i].second<N);
        assert(s.find(e[i])==s.end());
        s.insert(e[i]);
    }
    memset(vis,0,sizeof(vis));
    dfs(0,1);
    dfs(1,2);
    int A0=0,B0=0,C0=0;
    REP(u,N){
        assert(vis[u]!=0);
        if(vis[u]&1)A0++;
        if(vis[u]&2)B0++;
        if(vis[u]==3)C0++;
    }
    assert(A0==A and B0==B and C0==C);
}
int N;
int main(){
    vector<int> a,b,c;
    cin>>A>>B>>C>>D;
    if(A==C and B==C){
        if(A==1 or D<A){
            cout<<-1<<endl;
        }else{
            cout<<A<<" "<<A<<endl;
            REP(i,A){
                cout<<i<<" "<<(i+1)%A<<endl;
            }
        }
        return 0;
    }else if(A==C){
        c.push_back(0);
        int t = 2;
        REP(i,C-1)c.push_back(t++);
        b.push_back(1);
        REP(j,B-C-1)b.push_back(t++);
    }else if(B==C){
        c.push_back(1);
        int t = 2;
        REP(i,C-1)c.push_back(t++);
        a.push_back(0);
        REP(j,A-C-1)a.push_back(t++);
    }else{
        int t = 2;
        a.push_back(0);
        REP(i,A-C-1){
            a.push_back(t++);
        }
        b.push_back(1);
        REP(j,B-C-1){
            b.push_back(t++);
        }
        REP(k,C){
            c.push_back(t++);
        }
    }
    vector<pii> e;
    REP(i,a.size()){
        if(i+1<a.size())e.push_back(make_pair(a[i],a[i+1]));
    }
    REP(i,b.size()){
        if(i+1<b.size())e.push_back(make_pair(b[i],b[i+1]));
    }
    if(a.size()>0 and c.size()>0)e.push_back(make_pair(a.back(),c.front()));
    if(b.size()>0 and c.size()>0)e.push_back(make_pair(b.back(),c.front()));
    REP(i,c.size()){
        if(i+1<c.size())e.push_back(make_pair(c[i],c[i+1]));
    }
    int N = 0;
    REP(i,e.size()){
        N = max(N,e[i].first);
        N = max(N,e[i].second);
    }
    N++;
    N = max(N,2);
    if(D<e.size()){
//  if(false){
        cout<<-1<<endl;
    }else{
        cout<<N<<" "<<e.size()<<endl;
        REP(i,e.size()){
            cout<<e[i].first<<" "<<e[i].second<<endl;
        }
        check(N,e);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0