AtCoder Regular Contest 069

Submission #1180258

Source codeソースコード

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}
pii Dir[8] = { //移動
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};
class Graph {
public:
	int vn;
	int sumcost = 0;
	vector<vector<pii>> g;

	Graph(int n) {
		vn = n;
		g.resize(n);
	}
	virtual void con(int a, int b, int w) = 0;
	int getWeight(int f, int t) {
		auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN));
		if (itr != g[f].end())
			return itr->second;
		return INT_MIN;
	}
	int Costsum() {
		return sumcost;
	}
};

class BiDGraph : public Graph {//無向
public:
	BiDGraph(int n) : Graph(n) {}

	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		g[b].push_back({ a, w });
		sumcost++;
	}
};
class DGraph : public Graph {//有向
public:
	DGraph(int n) : Graph(n) {}
	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		sumcost++;
	}
};

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0;
	int k = 0;
	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}

bool TWO_SAT(int n, vector<pii> clause) {//否定は-, 1-indexed
	DGraph g(n * 2);
	for (auto itr : clause) {
		int a = (itr.first < 0 ? -itr.first+n : itr.first)-1, b = (itr.second < 0 ? -itr.second+ n : itr.second)-1;
		g.con(a + (a>=n?-n:n),b);
		g.con(b + (b >= n ? -n : n),a);
	}
	vector<int> scc;
	SCC(g, scc);

	REP(i, n) {
		if (scc[i] == scc[i + n]) {
			return 0;
		}
	}

	return 1;
}

signed main() {
	int n;
	scanf("%d", &n);
	vector<pii> flag(n, {-1,-1});
	vector<pii> ff(n*2);
	REP(i, n) {
		int a, b;
		scanf("%d %d", &a, &b);
		ff[i*2] = { a,i }; ff[i*2+1] = { b,i };
	}
	sort(ALL(ff));
	REP(i, 2 * n) {
		if(flag[ff[i].second].first!= -1)
			flag[ff[i].second].second = i;
		else
			flag[ff[i].second].first = i;
	}
	int l = 0, r = ff[n*2-1].first-ff[0].second+1; 

	int segs = 2,kk = 1;
	while (kk < n * 2) {
		kk *= 2; segs += kk;
	}
	while (1) {
		int mid = (l + r) / 2;

		vector<pii> clause;

		REP(i, n) {
			clause.push_back({ segs / 2 + flag[i].first,segs / 2 + flag[i].second });
			clause.push_back({ -(segs / 2 + flag[i].first),-(segs / 2 + flag[i].second) });
		}

		function<void(int, int, int, int, int)> cl = [&](int st, int a, int b, int num, int base) {
			if (b - a < 1) return;
			int left = (num-base) * (kk/base), right = (num - base + 1) * (kk / base);
			if (left == a && right == b) {
				clause.push_back({-st, -num});
			}
			else {	
				int nr = (left+right) / 2;
				if(nr > a) cl(st, a, min(b,nr), num*2, base*2);
				if(nr < b) cl(st, max(a,nr) , b, num * 2+1, base * 2);
			}
		};

		REP(i, n*2) {
			int ind = lower_bound(ALL(ff), MP(ff[i].first+mid, 0)) - ff.begin();
			cl(segs / 2 + i, i + 1, ind, 1, 1);
		}
		rep(i, 2, segs){
			clause.push_back({ -i, i / 2 });
		}

		if (TWO_SAT(segs, clause)) {
			l = mid;
		}
		else
			r = mid;

		if (r - l <= 1) {
			printf("%d\n", l);
			break;
		}
	}

	return 0;
}

Submission

Task問題 F - Flags
User nameユーザ名 もやし先輩
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 1200
Source lengthソースコード長 4814 Byte
File nameファイル名
Exec time実行時間 1321 ms
Memory usageメモリ使用量 26024 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 1200 / 1200 00_example_01.txt,00_example_02.txt,00_example_03.txt,01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 6 ms 888 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 2 ms 256 KB
01.txt AC 27 ms 1024 KB
02.txt AC 11 ms 588 KB
03.txt AC 4 ms 384 KB
04.txt AC 5 ms 384 KB
05.txt AC 5 ms 384 KB
06.txt AC 962 ms 23732 KB
07.txt AC 932 ms 22764 KB
08.txt AC 929 ms 22384 KB
09.txt AC 25 ms 1024 KB
10.txt AC 11 ms 576 KB
11.txt AC 4 ms 384 KB
12.txt AC 5 ms 384 KB
13.txt AC 5 ms 384 KB
14.txt AC 901 ms 23124 KB
15.txt AC 863 ms 22764 KB
16.txt AC 898 ms 22988 KB
17.txt AC 29 ms 1024 KB
18.txt AC 13 ms 568 KB
19.txt AC 972 ms 22764 KB
20.txt AC 988 ms 22864 KB
21.txt AC 1292 ms 24776 KB
22.txt AC 1304 ms 24556 KB
23.txt AC 1321 ms 24072 KB
24.txt AC 1226 ms 23728 KB
25.txt AC 1253 ms 26024 KB
26.txt AC 1050 ms 22660 KB
27.txt AC 1 ms 256 KB