Submission #669774
Source Code Expand
#ifndef KOMAKI_LOCAL
//#define NDEBUG
#endif
#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64 int64_t
#define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v) ((i64)((v).size()))
#define bit(n) (((i64)1)<<((i64)(n)))
#define all(v) (v).begin(), (v).end()
std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top(); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }
#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...) \
{ \
DBG_LINE(); \
DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
DBG_OUT << std::endl; \
}
class Timer
{
public:
void restart();
double getElapsed();
Timer();
private:
static double rdtsc_per_sec_inv;
double getTimeOfDay();
unsigned long long int getCycle();
double start_time;
unsigned long long int start_clock;
};
double Timer::rdtsc_per_sec_inv = -1;
inline double Timer::getElapsed()
{
if(rdtsc_per_sec_inv != -1) return (double)(getCycle() - start_clock) * rdtsc_per_sec_inv;
const double RDTSC_MEASUREMENT_INTERVAL = 0.1;
double res = getTimeOfDay() - start_time;
if(res <= RDTSC_MEASUREMENT_INTERVAL) return res;
rdtsc_per_sec_inv = 1.0 / (getCycle() - start_clock);
rdtsc_per_sec_inv *= getTimeOfDay() - start_time;
return getElapsed();
}
inline void Timer::restart()
{
start_time = getTimeOfDay();
start_clock = getCycle();
}
Timer::Timer()
{
restart();
}
inline double Timer::getTimeOfDay()
{
timeval tv;
gettimeofday(&tv,0);
return tv.tv_sec + tv.tv_usec * 0.000001;
}
inline unsigned long long int Timer::getCycle()
{
unsigned int low, high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}
Timer global_timer;
//#define LOCAL
#ifdef LOCAL
const i64 N = 30;
#else
const i64 N = 30;
#endif
const i64 H = 105;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int heights[N][N];
int up[N][N][H];
int down[N][N][H];
class Pos
{
public:
Pos(int x, int y, int h) : x(x), y(y), h(h) {}
int getIndex(){ return (h << 12) | (y << 6) | x; }
int x, y, h;
};
class Path
{
public:
Path(vector<Pos> positions) : positions(positions) {}
vector<Pos> positions;
int min_timestamp;
int max_timestamp;
};
vector<Path> greedy(bool shuffle_dirs=true)
{
//srand(time(NULL));
int t[N][N];
rep(x, N)rep(y, N) t[x][y] = heights[x][y];
vector<int> first_dirs = {0, 1, 2, 3};
vector<int> second_dirs = {3, 2, 1, 0};
if(shuffle_dirs){
random_shuffle(all(first_dirs));
random_shuffle(all(second_dirs));
}
vector<Path> paths;
while(true){
vector<pair<int, int>> survivers;
for(int x = 0; x < N; ++x){
for(int y = 0; y < N; ++y){
if(0 < t[x][y]) survivers.push_back(make_pair(x, y));
}
}
if(sz(survivers) == 0) break;
swap(survivers[0], survivers[rand() % sz(survivers)]);
rep(step, 3){
int i = rand() % sz(survivers);
int h0 = t[survivers[0].first][survivers[0].second];
int h1 = t[survivers[i].first][survivers[i].second];
if(h0 > h1) swap(survivers[0], survivers[i]);
}
int cx = survivers[0].first;
int cy = survivers[0].second;
while(true){
vector<int> dirs = first_dirs;
if(rand() % 2) random_shuffle(all(dirs));
int dir = -1;
rep(i, sz(dirs)){
int nx = cx + dx[dirs[i]];
int ny = cy + dy[dirs[i]];
if(nx < 0 || N <= nx) continue;
if(ny < 0 || N <= ny) continue;
if(t[nx][ny] <= t[cx][cy]) continue;
cx = nx;
cy = ny;
dir = dirs[i];
break;
}
if(dir == -1) break;
}
int ch = t[cx][cy] - 1;
vector<Pos> positions;
set<pair<int, int>> used;
while(true){
--t[cx][cy];
positions.push_back(Pos(cx, cy, ch--));
used.insert(make_pair(cx, cy));
vector<int> dirs = second_dirs;
int dir = -1;
rep(i, sz(dirs)){
int nx = cx + dx[dirs[i]];
int ny = cy + dy[dirs[i]];
if(nx < 0 || N <= nx) continue;
if(ny < 0 || N <= ny) continue;
if(t[nx][ny] != t[cx][cy] || t[nx][ny] == 0) continue;
if(used.count(make_pair(nx, ny))) continue;
cx = nx;
cy = ny;
dir = dirs[i];
break;
}
if(dir == -1) break;
}
paths.push_back(Path(positions));
}
return paths;
}
void setTimestamp(vector<Path> &paths)
{
unordered_map<int, int> pos_to_path_index;
vector<int> dependencies;
vector<int> ready;
for(Path &path: paths){
for(Pos &pos: path.positions){
pos_to_path_index[pos.getIndex()] = sz(dependencies);
}
dependencies.push_back(sz(path.positions));
}
rep(x, N)rep(y, N){
int index = pos_to_path_index[Pos(x, y, heights[x][y] - 1).getIndex()];
if(--dependencies[index] == 0) ready.push_back(index);
}
int timestamp = 0;
while(sz(ready)){
swap(ready.back(), ready[rand() % sz(ready)]);
int index = ready.back();
ready.pop_back();
paths[index].min_timestamp = timestamp;
paths[index].max_timestamp = timestamp;
++timestamp;
for(Pos &pos: paths[index].positions){
if(pos.h == 0) continue;
int i = pos_to_path_index[Pos(pos.x, pos.y, pos.h - 1).getIndex()];
if(--dependencies[i] == 0) ready.push_back(i);
}
}
rep(i, sz(dependencies)){
if(dependencies[i] == 0) continue;
for(Pos &pos : paths[i].positions){
}
}
assert(sz(paths) == timestamp);
}
void print(vector<Path> &paths)
{
setTimestamp(paths);
vector<pair<int, Path*>> sorted;
for(Path &path: paths) sorted.push_back(make_pair(path.min_timestamp, &path));
sort(all(sorted));
#ifdef LOCAL
DEBUG(sz(sorted));
#endif
for(pair<int, Path*> &path: sorted){
for(Pos &pos: path.second->positions){
#ifndef LOCAL
cout << pos.x + 1 << " " << pos.y + 1 << endl;
#endif
}
}
}
class Edge
{
public:
Edge() {}
Edge(int drop, int up, int down) : drop(drop), up(up), down(down) {}
int drop, up, down;
};
int visited_timestamp = 100;
int visited_dat[H << 12];
int reachability_dat[H << 12];
Edge graph_edges[H << 12];
bool checkReachability(int source, int sink)
{
int timestamp = ++visited_timestamp;
int *visited = visited_dat;
visited[source] = timestamp;
int *head = reachability_dat;
int *end = reachability_dat;
*(end++) = source;
while(head != end){
int pos = *(--end);
Edge &edge = graph_edges[pos];
{
int next = edge.up;
if(next != -1){
if(next == sink) return true;
if(visited[next] != timestamp){
visited[next] = timestamp;
*(end++) = next;
}
}
}
{
int next = edge.down;
if(next != -1){
if(next == sink) return true;
if(visited[next] != timestamp){
visited[next] = timestamp;
*(end++) = next;
}
}
}
{
int next = edge.drop;
if(next != -1){
if(next == sink) return true;
if(visited[next] != timestamp){
visited[next] = timestamp;
*(end++) = next;
}
}
}
}
return false;
}
vector<Path> connect(vector<Path> paths)
{
if(1){
vector<Path> dat = paths;
vector<pair<pair<int, pair<int, int>>, int>> v;
rep(i, sz(paths)) v.push_back(make_pair(make_pair(paths[i].positions.back().x, make_pair(paths[i].positions.back().y, paths[i].positions.back().h)), i));
sort(all(v));
if(rand() % 2) reverse(all(v));
paths.clear();
rep(i, sz(v)) paths.push_back(dat[v[i].second]);
}
unordered_map<int, int> top_pos_owner;
rep(i, sz(paths)) top_pos_owner[paths[i].positions[0].getIndex()] = i;
rep(x, N)rep(y, N) graph_edges[Pos(x, y, heights[x][y] - 1).getIndex()] = Edge(-1, -1, -1);
rep(x, N)rep(y, N)rep(h, heights[x][y] - 1) graph_edges[Pos(x, y, h + 1).getIndex()] = Edge(Pos(x, y, h).getIndex(), -1, -1);
for(Path &path0: paths){
rep(i, sz(path0.positions) - 1){
graph_edges[path0.positions[i + 0].getIndex()].down = path0.positions[i + 1].getIndex();
graph_edges[path0.positions[i + 1].getIndex()].up = path0.positions[i + 0].getIndex();
}
}
//DEBUG(global_timer.getElapsed());
int cnt = 0;
for(Path &path0: paths){
if(sz(path0.positions) == 0) continue;
while(true){
bool found = false;
vector<int> dirs = {3, 2, 1, 0};
//random_shuffle(all(dirs));
rep(_dir, 4){
int dir = dirs[_dir];
Pos pos = path0.positions.back();
int nx = pos.x + dx[dir];
int ny = pos.y + dy[dir];
if(nx < 0 || N <= nx) continue;
if(ny < 0 || N <= ny) continue;
if(pos.h == 0) continue;
int index = Pos(nx, ny, pos.h - 1).getIndex();
if(top_pos_owner.count(index) == 0 ) continue;
int pi = top_pos_owner[index];
if(pi == -1) continue;
if(checkReachability(index, pos.getIndex())) continue;
if(checkReachability(pos.getIndex(), index)) continue;
top_pos_owner[index] = -1;
graph_edges[pos.getIndex()].down = index;
graph_edges[index].up = pos.getIndex();
for(Pos &p: paths[pi].positions){
path0.positions.push_back(p);
}
paths[pi].positions.clear();
path0.max_timestamp = max(path0.max_timestamp, paths[pi].max_timestamp);
path0.min_timestamp = min(path0.min_timestamp, paths[pi].min_timestamp);
found = true;
++cnt;
}
if(!found) break;
for(Pos &p: path0.positions){
//cout << p.x << ", " << p.y << ", " << p.h << endl;
}
}
//if(3000 < cnt) break;
}
//DEBUG(global_timer.getElapsed());
vector<Path> res;
for(Path &path: paths){
if(sz(path.positions)) res.push_back(path);
}
#ifdef LOCAL
DEBUG(cnt);
DEBUG(sz(res), sz(paths));
#endif
return res;
}
/*
vector<Path> connect(vector<Path> paths)
{
unordered_map<int, int> top_pos_owner;
rep(i, sz(paths)) top_pos_owner[paths[i].positions[0].getIndex()] = i;
int cnt = 0;
for(Path &path0: paths){
if(sz(path0.positions) == 0) continue;
while(true){
bool found = false;
rep(dir, 4){
Pos pos = path0.positions.back();
int nx = pos.x + dx[dir];
int ny = pos.y + dy[dir];
if(nx < 0 || N <= nx) continue;
if(ny < 0 || N <= ny) continue;
if(pos.h == 0) continue;
int index = Pos(nx, ny, pos.h - 1).getIndex();
if(top_pos_owner.count(index) == 0 ) continue;
int pi = top_pos_owner[index];
if(pi == -1) continue;
if(!(paths[pi].max_timestamp < path0.min_timestamp)) continue;
top_pos_owner[index] = -1;
for(Pos &p: paths[pi].positions){
path0.positions.push_back(p);
}
paths[pi].positions.clear();
path0.max_timestamp = max(path0.max_timestamp, paths[pi].max_timestamp);
path0.min_timestamp = min(path0.min_timestamp, paths[pi].min_timestamp);
found = true;
++cnt;
#ifdef LOCAL
DEBUG(cnt);
#endif
}
if(!found) break;
for(Pos &p: path0.positions){
cout << p.x << ", " << p.y << ", " << p.h << endl;
}
}
if(3 < cnt) break;
}
vector<Path> res;
for(Path &path: paths){
if(sz(path.positions)) res.push_back(path);
}
#ifdef LOCAL
DEBUG(cnt);
DEBUG(sz(res), sz(paths));
#endif
return res;
}
*/
inline int getIndex(int x, int y)
{
return x * N + y;
}
inline double drand()
{
return rand() % 1000000 / 1000000.0;
}
/*
void solve0()
{
rep(x, N)rep(y, N)rep(h, H) up[x][y][h] = down[x][y][h] = -1;
//rep(x, N)rep(y, N)rep(h, height[x][y]) cout << x + 1 << " " << y + 1 << endl;
//return;
int current_score = 0;
rep(x, N)rep(y, N) current_score += heights[x][y];
int best_score = current_score;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
while(global_timer.getElapsed() <= 1.5){
int cx = rand() % N;
int cy = rand() % N;
int ch = rand() % heights[cx][cy];
int nd = rand() % 4;
int nx = cx + dx[nd];
int ny = cy + dy[nd];
if(nx < 0 || N <= nx) continue;
if(ny < 0 || N <= ny) continue;
if(down[cx][cy][ch] == nd) continue;
int nh = ch - 1;
if(nh < 0 || heights[nx][ny] <= nh) continue;
int pd = down[cx][cy][ch];
down[cx][cy][ch] = nd;
bool ok = true;
set<int> path;
path.insert(getIndex(cx, cy));
for(int x = cx, y = cy, h = ch; ok;){
if(down[x][y][h] == -1) break;
int xx = x + dx[down[x][y][h]];
int yy = y + dy[down[x][y][h]];
x = xx;
y = yy;
h = h - 1;
if(path.count(getIndex(x, y))) ok = false;
path.insert(getIndex(x, y));
}
for(int x = cx, y = cy, h = ch; ok;){
if(up[x][y][h] == -1) break;
int xx = x + dx[up[x][y][h]];
int yy = y + dy[up[x][y][h]];
x = xx;
y = yy;
h = h + 1;
if(path.count(getIndex(x, y))) ok = false;
path.insert(getIndex(x, y));
}
down[cx][cy][ch] = pd;
if(!ok) continue;
int score = 0;
if(down[cx][cy][ch] == -1) score += 1;
if(up[nx][ny][nh] != -1) score -= 1;
if(score == 1){
ok = true;
}else if(score == 0){
ok = false;//true;
}else if(score == -1){
ok = false;//drand() < 0.001;
}else{
assert(false);
}
if(!ok) continue;
if(up[nx][ny][nh] != -1){
int xx = nx + dx[up[nx][ny][nh]];
int yy = ny + dy[up[nx][ny][nh]];
down[xx][yy][ch] = -1;
}
if(down[cx][cy][ch] != -1){
int xx = cx + dx[down[cx][cy][ch]];
int yy = cy + dy[down[cx][cy][ch]];
up[xx][yy][nh] = -1;
}
up[nx][ny][nh] = nd ^ 2;
down[cx][cy][ch] = nd;
current_score -= score;
if(current_score < best_score){
best_score = current_score;
#ifdef LOCAL
cout << best_score << ", " << global_timer.getElapsed() << endl;
#endif
break;
}
}
{
map<pair<pair<int, int>, int>, int> path_index;
vector<vector<pair<pair<int, int>, int>>> paths;
vector<int> dependencies;
queue<int> ready;
rep(x, N)rep(y, N)rep(h, heights[x][y]){
if(up[x][y][h] != -1){
continue;
}
vector<pair<pair<int, int>, int>> path;
path.push_back(make_pair(make_pair(x, y), h));
path_index[make_pair(make_pair(x, y), h)] = sz(paths);
for(int xx = x, yy = y, hh = h; true;){
if(down[xx][yy][hh] == -1) break;
int xxx = xx + dx[down[xx][yy][hh]];
int yyy = yy + dy[down[xx][yy][hh]];
xx = xxx;
yy = yyy;
hh = hh - 1;
path.push_back(make_pair(make_pair(xx, yy), hh));
path_index[make_pair(make_pair(xx, yy), hh)] = sz(paths);
}
dependencies.push_back(sz(path));
paths.push_back(path);
}
DEBUG0();
rep(x, N)rep(y, N){
int h = heights[x][y] - 1;
int index = path_index[make_pair(make_pair(x, y), h)];
if(--dependencies[index] == 0) ready.push(index);
}
DEBUG0();
int debug_cnt = 0;
while(sz(ready)){
int index = ready.front();
ready.pop();
for(pair<pair<int, int>, int> pos: paths[index]){
int x = pos.first.first;
int y = pos.first.second;
#ifndef LOCAL
cout << x + 1 << " " << y + 1 << endl;
#endif
++debug_cnt;
int h = pos.second;
if(h == 0) continue;
int i = path_index[make_pair(make_pair(x, y), h - 1)];
if(--dependencies[i] == 0) ready.push(i);
}
}
int total_height = 0;
rep(x, N)rep(y, N) total_height += heights[x][y];
DEBUG(debug_cnt);
DEBUG(total_height);
}
}
*/
void test()
{
cout << "start testing" << endl;
exit(0);
}
void readInput()
{
rep(i, N)rep(j, N) cin >> heights[i][j];
}
void randomInput()
{
//srand(13521521);
//srand(time(NULL));
rep(i, N)rep(j, N) heights[i][j] = rand() % 100 + 1;
}
int main()
{
// test();
global_timer.restart();
#ifdef LOCAL
int test_case = 1;
#else
int test_case = 0;
#endif
vector<vector<int>> mp;
switch(test_case){
case 0:
readInput();
break;
case 1:
randomInput();
break;
default:
assert(false);
}
vector<Path> best_paths = greedy(false);
best_paths = connect(best_paths);
while(global_timer.getElapsed() < 7.0){
vector<Path> paths = greedy();
rep(i, 2){
vector<Path> ps = greedy();
if(sz(ps) < sz(paths)) paths = ps;
}
paths = connect(paths);
if(sz(paths) < sz(best_paths)){
best_paths = paths;
}
}
print(best_paths);
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
Komaki |
Language |
C++14 (GCC 5.4.1) |
Score |
885566 |
Code Size |
20692 Byte |
Status |
AC |
Exec Time |
8562 ms |
Memory |
10324 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
88943 / 100000 |
88413 / 100000 |
88787 / 100000 |
88220 / 100000 |
88511 / 100000 |
88285 / 100000 |
88640 / 100000 |
88570 / 100000 |
88671 / 100000 |
88526 / 100000 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
7994 ms |
9776 KB |
subtask_01_02.txt |
AC |
8395 ms |
9780 KB |
subtask_01_03.txt |
AC |
7917 ms |
9488 KB |
subtask_01_04.txt |
AC |
8562 ms |
10324 KB |
subtask_01_05.txt |
AC |
8334 ms |
10132 KB |
subtask_01_06.txt |
AC |
7413 ms |
10112 KB |
subtask_01_07.txt |
AC |
8424 ms |
10224 KB |
subtask_01_08.txt |
AC |
8479 ms |
10008 KB |
subtask_01_09.txt |
AC |
8335 ms |
10112 KB |
subtask_01_10.txt |
AC |
7372 ms |
9680 KB |