#include<iostream>
#include<fstream>
#include<sstream>
#include<assert.h>
#include<chrono>
#include<math.h>
#include<algorithm>
#include<future>
#include<vector>
#include<unordered_map>
#include<set>
#include<string>
#include<sys/mman.h>
#include<sys/types.h>
#include<fcntl.h>
#include<string.h>
#include<stdio.h>
#include<unistd.h>
using namespace std;
typedef unsigned int uint;
#define TEST
#ifdef TEST
string FileName = "/home/li/test_data_196.txt";
string outFileName = "result.txt";
#endif
#ifdef EXAM
string FileName = "/data/test_data.txt";
string outFileName = "/projects/student/result.txt";
#endif
const uint UI_MAX = 4294967295;
const uint UI_MAX_3 = 4294967295 / 3;
const unsigned int THREAD_NUM = 4;
const uint ANSWER_NUMBER = 20000000 / THREAD_NUM;
struct m_answer {
char c[80] = {};
};
vector<m_answer> ring_result[THREAD_NUM][5];
vector<uint> ring_result_stat[THREAD_NUM][5];
unsigned int m_map_size = 0;
#ifdef TEST
class Timer
{
public:
Timer() : beg_(clock_::now()) {}
void reset() { beg_ = clock_::now(); }
double elapsed() const {
return std::chrono::duration_cast<second_>
(clock_::now() - beg_).count();
}
void out(std::string message = "") {
double t = elapsed();
std::cout << message << "\nelasped time:" << t << "s" << std::endl;
reset();
}
private:
typedef std::chrono::high_resolution_clock clock_;
typedef std::chrono::duration<double, std::ratio<1> > second_;
std::chrono::time_point<clock_> beg_;
};
#endif
struct m_limit {
uint low;
uint high;
};
struct arc {
uint id;
uint money;
m_limit limit;
arc() {};
arc(uint &a, uint &b) :id(a), money(b)
{
limit.low = ceil(money*0.2);
limit.high = money>(UI_MAX_3) ? UI_MAX : money * 3;
};
void setMoney(uint &m)
{
money = m;
limit.low = ceil(money*0.2);
limit.high = money>(UI_MAX_3) ? UI_MAX : money * 3;
}
};
struct node {
vector<arc> c_arc;
vector<arc> f_arc;
uint forward_state[THREAD_NUM];
uint back_state[THREAD_NUM];
uint id;
char id_char[12];
node()
{
c_arc.reserve(32);
f_arc.reserve(32);
for (int i = 0; i < THREAD_NUM; ++i)
{
forward_state[i] = -1;
back_state[i] = -1;
}
}
};
vector<node> m_map;
bool arcCMP(arc &v1, arc &v2)
{
return v1.id < v2.id;
}
void my_itoa(char* buf, unsigned int val)
{
unsigned int vals[10] = {};
int len = 0;
do
{
vals[len] = val % 10;
val /= 10;
++len;
} while (val > 0);
--len;
char* p = buf;
do
{
*p = vals[len] + '0';
++p;
--len;
} while (len >= 0);
*p = ',';
++p;
*p = '\0';
}
inline void ui2S(vector<unsigned int>&a, vector<m_answer> &b, vector<uint> &c)
{
c.push_back(a[0]);
m_answer s_temp;
char *p1 = s_temp.c;
char *p2 ;
for (unsigned int i = 0; i < a.size(); ++i)
{
p2 = m_map[a[i]].id_char;
while (*p2 != '\0')
{
*p1 = *p2;
++p1;
++p2;
}
}
*p1 = '\0';
--p1;
*p1 = '\n';
b.push_back(s_temp);
}
void BuildG()
{
set<uint> ordered_set;
unordered_map<uint, uint> node_map;
unordered_multimap<uint, arc> arc_map;
int fd = open(FileName.c_str(), O_RDONLY);
int len = lseek(fd, 0, SEEK_END);
char* data = (char*)mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
close(fd);
auto p_end = data;
unsigned int value[3];
while (*p_end != '\0')
{
for (short int i = 0; i < 3; ++i)
{
value[i] = strtoul(p_end, &p_end, 10);
++p_end;
}
ordered_set.insert(value[0]);
node_map.insert(pair<uint, uint>(value[0], 1));
if (value[2] != 0)
{
arc temp(value[1], value[2]);
arc_map.insert(pair<uint, arc>(value[0], temp));
}
}
munmap(data, len);
m_map_size = ordered_set.size();
m_map.resize(m_map_size);
auto temp_iter = ordered_set.begin();
node temp_node;
for (unsigned int i = 0; i < m_map_size; ++i)
{
m_map[i].id = *temp_iter;
my_itoa(m_map[i].id_char, m_map[i].id);
node_map[*temp_iter] = i;
++temp_iter;
}
for (unsigned int i = 0; i < m_map_size; ++i)
{
unsigned int count = arc_map.count(m_map[i].id);
auto iter = arc_map.find(m_map[i].id);
arc temp_arc;
uint temp;
while (count)
{
if (node_map.count(iter->second.id))
{
temp_arc.id = node_map[iter->second.id];
temp_arc.setMoney(iter->second.money);
m_map[i].c_arc.push_back(temp_arc);
temp = temp_arc.id;
temp_arc.id = i;
m_map[temp].f_arc.push_back(temp_arc);
}
--count;
++iter;
}
sort(m_map[i].c_arc.begin(), m_map[i].c_arc.end(), arcCMP);
}
}
void findForward(vector<uint> &index_vector, const uint &process_index, const uint &thread_index)
{
for (arc &child1 : m_map[process_index].c_arc)
{
if (child1.id > process_index)
{
index_vector.push_back(child1.id);
m_map[child1.id].forward_state[thread_index] = process_index;
for (arc &child2 : m_map[child1.id].c_arc)
{
if (child2.id > process_index &&
(child2.money >= child1.limit.low && child2.money <= child1.limit.high))
{
index_vector.push_back(child2.id);
m_map[child2.id].forward_state[thread_index] = process_index;
for (arc &child3 : m_map[child2.id].c_arc)
{
if (child3.id == process_index)
{
if ((child3.money >= child2.limit.low && child3.money <= child2.limit.high) &&
child1.money >= child3.limit.low && child1.money <= child3.limit.high)
{
ui2S(index_vector, ring_result[thread_index][0], ring_result_stat[thread_index][0]);
}
continue;
}
if (child3.id > process_index &&
m_map[child3.id].forward_state[thread_index] != process_index &&
(child3.money >= child2.limit.low && child3.money <= child2.limit.high))
{
index_vector.push_back(child3.id);
m_map[child3.id].forward_state[thread_index] = process_index;
for (arc &child4 : m_map[child3.id].c_arc)
{
if (child4.id == process_index)
{
if ((child4.money >= child3.limit.low && child4.money <= child3.limit.high) &&
child1.money >= child4.limit.low && child1.money <= child4.limit.high)
{
ui2S(index_vector, ring_result[thread_index][1], ring_result_stat[thread_index][1]);
}
continue;
}
if (m_map[child4.id].back_state[thread_index] == process_index&&
m_map[child4.id].forward_state[thread_index] != process_index &&
(child4.money >= child3.limit.low && child4.money <= child3.limit.high))
{
index_vector.push_back(child4.id);
m_map[child4.id].forward_state[thread_index] = process_index;
for (arc &child5 : m_map[child4.id].c_arc)
{
if (child5.id == process_index)
{
if ((child5.money >= child4.limit.low && child5.money <= child4.limit.high) &&
child1.money >= child5.limit.low && child1.money <= child5.limit.high)
{
ui2S(index_vector, ring_result[thread_index][2], ring_result_stat[thread_index][2]);
}
continue;
}
if (m_map[child5.id].back_state[thread_index] == process_index&&
m_map[child5.id].forward_state[thread_index] != process_index&&
child5.money >= child4.limit.low && child5.money <= child4.limit.high)
{
index_vector.push_back(child5.id);
for (arc &child6 : m_map[child5.id].c_arc)
{
if (child6.id == process_index)
{
if (child6.money >= child5.limit.low && child6.money <= child5.limit.high &&
child1.money >= child6.limit.low && child1.money <= child6.limit.high)
{
ui2S(index_vector, ring_result[thread_index][3], ring_result_stat[thread_index][3]);
}
continue;
}
if (m_map[child6.id].back_state[thread_index] == process_index&&
m_map[child6.id].forward_state[thread_index] != process_index&&
child6.money >= child5.limit.low && child6.money <= child5.limit.high)
{
for (arc &child7 : m_map[child6.id].c_arc)
{
if (child7.id == process_index&&
child7.money >= child6.limit.low && child7.money <= child6.limit.high&&
child1.money >= child7.limit.low && child1.money <= child7.limit.high)
{
index_vector.push_back(child6.id);
ui2S(index_vector, ring_result[thread_index][4], ring_result_stat[thread_index][4]);
index_vector.pop_back();
break;
}
}
}
}
index_vector.pop_back();
}
}
index_vector.pop_back();
m_map[child4.id].forward_state[thread_index] = -1;
}
}
index_vector.pop_back();
m_map[child3.id].forward_state[thread_index] = -1;
}
}
m_map[child2.id].forward_state[thread_index] = -1;
index_vector.pop_back();
}
}
m_map[child1.id].forward_state[thread_index] = -1;
index_vector.pop_back();
}
}
}
void findBack(const uint &process_index, const uint &thread_index)
{
for (arc &father1 : m_map[process_index].f_arc)
{
if (father1.id > process_index)
{
m_map[father1.id].forward_state[thread_index] = process_index;
m_map[father1.id].back_state[thread_index] = process_index;
for (arc &father2 : m_map[father1.id].f_arc)
{
if (father2.id > process_index && (father1.money >= father2.limit.low &&father1.money <= father2.limit.high) &&
m_map[father2.id].forward_state[thread_index] != process_index)
{
m_map[father2.id].forward_state[thread_index] = process_index;
m_map[father2.id].back_state[thread_index] = process_index;
for (arc &father3 : m_map[father2.id].f_arc)
{
if (father3.id > process_index && (father2.money >= father3.limit.low &&father2.money <= father3.limit.high) &&
m_map[father3.id].forward_state[thread_index] != process_index)
{
m_map[father3.id].back_state[thread_index] = process_index;
}
}
m_map[father2.id].forward_state[thread_index] = -1;
}
}
m_map[father1.id].forward_state[thread_index] = -1;
}
}
}
bool FindRingT(const unsigned int thread_index)
{
for (int i = 0; i < 5; ++i)
{
ring_result[thread_index][i].reserve(ANSWER_NUMBER);
ring_result_stat[thread_index][i].reserve(ANSWER_NUMBER);
}
unsigned int i = thread_index;
vector<unsigned int > index_vector;
index_vector.reserve(7);
while (i < m_map_size)
{
index_vector.clear();
index_vector.push_back(i);
m_map[i].forward_state[thread_index] = i;
findBack(i, thread_index);
findForward(index_vector, i, thread_index);
i += THREAD_NUM;
if (i % 1000 == 0)
{
}
}
return true;
}
int main()
{
Timer time0;
BuildG();
time0.out();
Timer time1;
std::future<bool> m[THREAD_NUM - 1];
for (uint i = 0; i < THREAD_NUM - 1; ++i)
{
m[i] = std::async(FindRingT, i);
}
FindRingT(THREAD_NUM - 1);
for (uint i = 0; i < THREAD_NUM - 1; ++i)
{
m[i].wait();
}
time1.out();
uint size[5] = { 0,0,0,0,0 };
uint total_size = 0;
for (uint i = 0; i < THREAD_NUM; ++i)
{
for (uint j = 0; j < 5; ++j)
{
size[j] += ring_result[i][j].size();
total_size += ring_result[i][j].size();
}
}
int len = total_size * 80;
int fd = open(outFileName.c_str(), O_RDWR | O_CREAT, 0666);
lseek(fd, len - 1, SEEK_END);
write(fd, "", 1);
char* addr = (char*)mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
close(fd);
auto iter = addr;
string total_size_s = to_string(total_size) + "\n";
memcpy(addr, total_size_s.c_str(), total_size_s.size());
addr += total_size_s.size();
uint t[THREAD_NUM];
uint process_id = 0;
for (uint i = 0; i < 5; ++i)
{
for (uint j = 0; j < THREAD_NUM; ++j)
t[j] = 0;
process_id = 0;
while (size[i])
{
for (uint j = 0; j < THREAD_NUM; ++j)
{
while (t[j] < ring_result_stat[j][i].size() && ring_result_stat[j][i][t[j]] == process_id)
{
memcpy(addr, ring_result[j][i][t[j]].c, strlen(ring_result[j][i][t[j]].c));
addr += strlen(ring_result[j][i][t[j]].c);
++t[j];
--size[i];
}
++process_id;
}
}
}
memcpy(addr, "\0", 1);
munmap(iter, len);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)