プログラマ専用SNS ミクプラ

コード:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int start;
	unsigned int end;
} range_t;

int comp(const void* x,const void* y) {
	range_t* a=(range_t*)x;
	range_t* b=(range_t*)y;
	if(a->start>b->start)return 1;
	if(a->start<b->start)return -1;
	if(a->end>b->end)return 1;
	if(a->end<b->end)return -1;
	return 0;
}

int main(void) {
	int datanum;
	int i;
	int resultnum;
	range_t input[10000];
	range_t result[10000];
	scanf("%d",&datanum);
	for(i=0;i<datanum;i++) {
		scanf("%u %u",&input[i].start,&input[i].end);
	}
	qsort(input,datanum,sizeof(range_t),comp);
	resultnum=1;
	result[0].start=input[0].start;
	result[0].end=input[0].end;
	for(i=1;i<datanum;i++) {
		if(input[i].start<=result[resultnum-1].end+1) {
			if(input[i].end>result[resultnum-1].end) {
				result[resultnum-1].end=input[i].end;
			}
		} else {
			result[resultnum].start=input[i].start;
			result[resultnum].end=input[i].end;
			resultnum++;
		}
	}
	for(i=0;i<resultnum;i++) {
		printf("%u %u\n",result[i].start,result[i].end);
	}
	return 0;
}

コード:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef std::pair<size_t, size_t> RangeType;

void MergePushRange(std::vector<RangeType>& range_data, const RangeType& range)
{
	if (range_data.empty() || range_data.back().second + 1 < range.first)
	{
		range_data.push_back(range);
	}
	else
	{
		range_data.back().second = range.second;
	}
}

int main()
{
	size_t numdata = 0;
	cin >> numdata;

	vector<RangeType> range_data;
	RangeType r;
	for (size_t i = 0; i < numdata; ++i)
	{
		cin >> r.first >> r.second;
		range_data.push_back(r);
	}

	sort(range_data.begin(), range_data.end(), [](const RangeType& a, const RangeType& b)
	{
		return a.first < b.first || a.second < b.second;
	});

	vector<RangeType> result;
	for (auto it = range_data.begin(); it != range_data.end(); ++it)
	{
		MergePushRange(result, *it);
	}

	for (auto it = result.begin(); it != result.end(); ++it)
	{
		cout << it->first << ' ' << it->second << endl;
	}
}

コード:

#include <iostream>
#include <set>
#include <utility>
#include <algorithm>

typedef std::pair<int, int> range;
typedef std::set<range> range_set;

void add(range_set &ranges, range r)
{
	range_set::iterator it;

	// r ⊆ x なる x が存在する場合
	// r は不要なので終了
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first <= r.first && r.second <= x.second;
	});
	if (it != ranges.end()) {
		return;
	}

	// x ⊆ r なる x が存在する場合
	// x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return r.first <= x.first && x.second <= r.second;
	});
	if (it != ranges.end()) {
		ranges.erase(it);
	}

	// r が x の右側にくっついてる場合
	// r を左側に伸ばし、x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first <= r.first && r.first <= x.second + 1;
	});
	if (it != ranges.end()) {
		r.first = it->first;
		ranges.erase(it);
	}

	// r が x の左側にくっついてる場合
	// r を右に伸ばし、x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first - 1 <= r.second && r.second <= x.second;
	});
	if (it != ranges.end()) {
		r.second = it->second;
		ranges.erase(it);
	}

	// 追加
	ranges.insert(r);
}

int main()
{
	int n;
	std::cin >> n;
	range_set ranges;
	while (n--) {
		range r;
		std::cin >> r.first >> r.second;
		add(ranges, r);
	}
	std::for_each(ranges.begin(), ranges.end(), [](range r) {
		std::cout << r.first << " " << r.second << std::endl;
	});
	return 0;
}

コード:

import java.awt.geom.*;
import java.io.*;
import java.util.*;

class Range implements Comparable<Range>
{
	private Line2D.Double line;

	public Range(int xMin, int xMax)
	{
		line = new Line2D.Double(xMin - 0.5, 0, xMax + 0.5, 0);
	}

	public static boolean combine(Range r1, Range r2)
	{
		if (r1.line.intersectsLine(r2.line))
		{
			r1.line.x1 = Math.min(r1.line.x1, r2.line.x1);
			r1.line.x2 = Math.max(r1.line.x2, r2.line.x2);

			r2.line.setLine(r1.line);

			return true;
		}
		return false;
	}

	public int getIntX1()
	{
		return (int)(line.x1 + 0.5);
	}

	public int getIntX2()
	{
		return (int)(line.x2 - 0.5);
	}

	public int compareTo(Range r)
	{
		Line2D.Double l1 = this.line, l2 = r.line;

		if (l1.x1 < l2.x1)
		{
			return -1;
		}
		else if (l1.x1 == l2.x1)
		{
			if (l1.x2 < l2.x2)
			{
				return -1;
			}
			else if (l1.x2 == l2.x2)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		else
		{
			return 1;
		}
	}
}

public class Main
{
	public static void main(String[] args) throws IOException
	{
		TreeSet<Range> inputSet = new TreeSet<>();

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in)))
		{
			int n = Integer.parseInt(br.readLine());

			for (int i = 0; i < n; i++)
			{
				String[] s = br.readLine().split(" ");

				inputSet.add(new Range(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
			}

			TreeSet<Range> set = new TreeSet<>(
				new Comparator<Range>()
				{
					public int compare(Range r1, Range r2)
					{
						if (Range.combine(r1, r2))
						{
							return 0;
						}
						return r1.compareTo(r2);
					}
				});
			set.addAll(inputSet);

			for (Range r : set)
			{
				System.out.printf("%d %d\n", r.getIntX1(), r.getIntX2());
			}
		}
		catch (IOException ioe)
		{}
	}
}

コード:

#include <iostream>
#include <map>
#include <utility>

template <typename Key0, typename Key1, typename Value0, typename Value1>
inline bool Intersect(const std::pair<Key0, Value0>& range0, const std::pair<Key1, Value1>& range1)
{
    // must be range0.first <= range1.first
    return range1.first <= range0.second + 1;
}

template <typename Key0, typename Key1, typename Value0, typename Value1>
inline bool Enclose(const std::pair<Key0, Value0>& range0, const std::pair<Key1, Value1>& range1)
{
    // must be range0.first <= range1.first
    return range1.second <= range0.second;
}

template <typename Key, typename Value>
std::pair<Key, Value> MergeAndErase(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& next)
{
    auto it = next;
    while (it != ranges.end() && Enclose(range, *it))
    {
        it = ranges.erase(it);
    }
    if (it != ranges.end() && Intersect(range, *it))
    {
        range.second = it->second;
        it = ranges.erase(it);
    }
    return range;
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& next)
{
    range = MergeAndErase(ranges, range, next);
    ranges.insert(range);
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& prev, const typename std::map<Key, Value>::iterator& next)
{
    if (Intersect(*prev, range))
    {
        range = MergeAndErase(ranges, range, next);
        if (prev->second < range.second)
        {
            prev->second = range.second;
        }
    }
    else
    {
        InsertOrMerge(ranges, range, next);
    }
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, const std::pair<Key, Value>& range)
{
    if (ranges.empty())
    {
        ranges.insert(range);
    }
    else
    {
        auto next = ranges.lower_bound(range.first);

        if (next != ranges.begin())
        {
            auto prev = next;
            --prev;
            InsertOrMerge(ranges, range, prev, next);
        }
        else
        {
            InsertOrMerge(ranges, range, next);
        }
    }
}

int main()
{
    using namespace std;
    typedef long IntType;

    map<IntType, IntType> ranges;

    size_t numdata = 0;
    cin >> numdata;

    IntType a = 0, b = 0;
    for (size_t i = 0; i < numdata; ++i)
    {
        cin >> a >> b;
        InsertOrMerge(ranges, make_pair(a, b));
    }

    for (auto it = ranges.begin(); it != ranges.end(); ++it)
    {
        cout << it->first << " " << it->second << endl;
    }
}

コード:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace VS_Apache_Killer
{
    class Range
    {
        public uint beg { set; get; }
        public uint end { set; get; }
        public override string ToString()
        {
            return beg + " " + end;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                var rangeNum = int.Parse(Console.ReadLine());
                var ranges = new List<Range>(rangeNum);

                for (var i = 0; i < rangeNum; ++i)
                {
                    var buf = Console.ReadLine().Split(' ');
                    ranges.Add(new Range() { beg = uint.Parse(buf[0]), end = uint.Parse(buf[1]) });
                }
                ranges.Sort((a, b) =>
                {
                    if (b.beg < a.beg && b.end < a.end)
                    {
                        return 1;
                    }
                    else if(a.beg < b.beg && a.end < b.end)
                    {
                        return -1;
                    }
                    return 0;
                });
                var results = new List<Range>();
                results.Add(ranges[0]);
                for(var i = 1 ; i < ranges.Count ; ++i)
                {
                    var last = results.Last();
                    if (ranges[i].beg > last.end + 1) /*0-1 3-5等*/
                    {
                        results.Add(ranges[i]);
                    }
                    else /*1-2 0-4, 0-4 2-5 等*/
                    {
                        last.beg = Math.Min(last.beg, ranges[i].beg);
                        last.end = Math.Max(last.end, ranges[i].end);
                    }
                }
                Console.WriteLine("results");
                results.ForEach(Console.WriteLine);
            }
            catch (Exception e)
            {
                Debug.Print(e.ToString());
            }
        }
    }
}

コード:

#!/usr/bin/python
import subprocess
import sys
import os.path

if len(sys.argv) != 2:
	exit(-1)

# テストケース名には、とりあえず0から999までの番号を使う
numfile = 1000

for i in range(0, numfile):
	# テストケース名を生成
	in_name = "%d.in" % (i, )
	out_name = "%d.out" % (i, )
	# テストケースファイルが存在するか確認
	if not os.path.exists(in_name) or not os.path.exists(out_name):
		continue
	# テストケースファイルを開く
	in_file = open(in_name)
	out_file = open(out_name)
	
	# テスト実行（引数で指定されたアプリを実行し、出力を比べる）
	p = subprocess.Popen("%s < %d.in | diff - %d.out | wc -c" % (sys.argv[1], i, i),
			shell = True, cwd = "./",
			stdin = subprocess.PIPE,
			stdout = subprocess.PIPE)
	p.wait()
	# 出力とテストケースに差がないか調べる
	if p.stdout.readline() == "0\n":
		# 差が0バイトである
		print("test %d OK" % (i, ))
	else:
		print("test %d FAILED" % (i, ))