Submission #1295211
Source Code Expand
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;
void stronglyConnectedComponents(const vector<vector<int> >& edges, vector<int>& indexConvert,
vector<vector<int> >& nodesOut, vector<vector<int> >& edgesOut)
{
const int n = edges.size();
vector<int> num(n, -1), low(n, -1);
vector<bool> isStk(n, false);
stack<int> stk;
int cnt = -1;
nodesOut.clear();
for(int i=0; i<n; ++i){
stack<pair<int, unsigned> > arg;
arg.push(make_pair(i, 0));
while(!arg.empty()){
int v = arg.top().first;
unsigned j = arg.top().second;
arg.pop();
if(j == 0){
if(num[v] != -1)
continue;
num[v] = low[v] = ++ cnt;
stk.push(v);
isStk[v] = true;
}
else{
int w = edges[v][j-1];
if(isStk[w])
low[v] = min(low[v], low[w]);
}
if(j < edges[v].size()){
arg.push(make_pair(v, j + 1));
int w = edges[v][j];
arg.push(make_pair(w, 0));
}
else if(low[v] == num[v]){
nodesOut.push_back(vector<int>());
for(;;){
int w = stk.top();
stk.pop();
isStk[w] = false;
nodesOut.back().push_back(w);
if(v == w)
break;
}
}
}
}
reverse(nodesOut.begin(), nodesOut.end()); // DAGにするために反転させる
const int m = nodesOut.size();
indexConvert.resize(n);
for(int i=0; i<m; ++i){
for(unsigned j=0; j<nodesOut[i].size(); ++j)
indexConvert[nodesOut[i][j]] = i;
}
edgesOut.assign(m, vector<int>());
vector<set<int> > used(m);
for(int i=0; i<n; ++i){
for(unsigned j=0; j<edges[i].size(); ++j){
int v = indexConvert[i];
int w = indexConvert[edges[i][j]];
if(v != w && used[v].find(w) == used[v].end()){
edgesOut[v].push_back(w);
used[v].insert(w);
}
}
}
}
bool is2sat(int n, const vector<pair<int, bool> >& cs, vector<bool>& ans)
{
vector<vector<int> > edges1(2*n);
for(unsigned i=0; i<cs.size(); i+=2){
int a = cs[i].first * 2 + (cs[i].second ? 0 : 1);
int b = cs[i+1].first * 2 + (cs[i+1].second ? 0 : 1);
edges1[a^1].push_back(b);
edges1[b^1].push_back(a);
}
vector<int> indexConvert;
vector<vector<int> > nodes, edges2;
stronglyConnectedComponents(edges1, indexConvert, nodes, edges2);
ans.resize(n);
for(int i=0; i<n; ++i){
if(indexConvert[2*i] < indexConvert[2*i+1])
ans[i] = false;
else if(indexConvert[2*i+1] < indexConvert[2*i])
ans[i] = true;
else
return false;
}
return true;
}
class SegmentTree
{
private:
int n;
void getRangeIndex(int a, int b, int k, int l, int r, vector<int>& index){
if(a <= l && r <= b){
index.push_back(k);
}
else if(a <= r && l <= b){
getRangeIndex(a, b, k*2+1, l, (l+r)/2, index);
getRangeIndex(a, b, k*2+2, (l+r+1)/2, r, index);
}
}
public:
SegmentTree(int n0){
n = 1;
while(n < n0)
n *= 2;
}
int getNodeNum(){
return 2 * n - 1;
}
int getLeafIndex(int a){
return n - 1 + a;
}
int getParentIndex(int a){
if(a == 0)
return -1;
else
return (a - 1) / 2;
}
void getRangeIndex(int a, int b, vector<int>& index){
index.clear();
return getRangeIndex(a, b, 0, 0, n-1, index);
}
};
int main()
{
int n;
cin >> n;
vector<pair<int, int> > flag(2*n);
for(int i=0; i<2*n; ++i){
cin >> flag[i].first;
flag[i].second = i;
}
sort(flag.begin(), flag.end());
vector<int> index(2*n);
for(int i=0; i<2*n; ++i)
index[flag[i].second] = i;
SegmentTree st(2*n);
int m = st.getNodeNum();
int left = 0;
int right = 1000000000;
while(left < right){
vector<pair<int, bool> > cs;
for(int a=1; a<m; ++a){
int b = st.getParentIndex(a);
cs.push_back(make_pair(a, false));
cs.push_back(make_pair(b, true));
}
for(int i=0; i<n; ++i){
cs.push_back(make_pair(st.getLeafIndex(index[2*i]), true));
cs.push_back(make_pair(st.getLeafIndex(index[2*i+1]), true));
}
int mid = (left + right + 1) / 2;
int j = 0;
for(int i=0; i<2*n; ++i){
while(flag[i].first - flag[j].first >= mid)
++ j;
vector<int> v;
st.getRangeIndex(j, i-1, v);
for(int a : v){
cs.push_back(make_pair(st.getLeafIndex(i), false));
cs.push_back(make_pair(a, false));
}
}
vector<bool> tmp;
if(is2sat(m, cs, tmp))
left = mid;
else
right = mid - 1;
}
cout << left << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
mamekin |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
5897 Byte |
Status |
AC |
Exec Time |
3364 ms |
Memory |
50748 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
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 |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
2 ms |
256 KB |
00_example_02.txt |
AC |
2 ms |
256 KB |
00_example_03.txt |
AC |
5 ms |
256 KB |
01.txt |
AC |
77 ms |
1528 KB |
02.txt |
AC |
39 ms |
904 KB |
03.txt |
AC |
10 ms |
460 KB |
04.txt |
AC |
19 ms |
592 KB |
05.txt |
AC |
19 ms |
576 KB |
06.txt |
AC |
2975 ms |
38716 KB |
07.txt |
AC |
3017 ms |
38692 KB |
08.txt |
AC |
2985 ms |
38752 KB |
09.txt |
AC |
78 ms |
1524 KB |
10.txt |
AC |
40 ms |
900 KB |
11.txt |
AC |
10 ms |
448 KB |
12.txt |
AC |
19 ms |
596 KB |
13.txt |
AC |
19 ms |
596 KB |
14.txt |
AC |
2989 ms |
38944 KB |
15.txt |
AC |
2980 ms |
38928 KB |
16.txt |
AC |
2974 ms |
38860 KB |
17.txt |
AC |
78 ms |
1656 KB |
18.txt |
AC |
38 ms |
940 KB |
19.txt |
AC |
3091 ms |
43524 KB |
20.txt |
AC |
3132 ms |
43532 KB |
21.txt |
AC |
2787 ms |
31080 KB |
22.txt |
AC |
2750 ms |
31360 KB |
23.txt |
AC |
3194 ms |
30812 KB |
24.txt |
AC |
2959 ms |
32600 KB |
25.txt |
AC |
2987 ms |
30620 KB |
26.txt |
AC |
3364 ms |
50748 KB |
27.txt |
AC |
1 ms |
256 KB |