Submission #2086597

---

Source Code Expand

#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>
#include <chrono>
using namespace std;

//forked mamekin's code
class TicToc
{
private:
	double getCurrTime(){
	#ifdef MAMEKIN_PC
		return GetTickCount() * 1e-3;
	#else
		struct timeval tv;
		gettimeofday(&tv, NULL);
		return tv.tv_sec + tv.tv_usec * 1e-6;
	#endif
	}
	double startTime;
public:
	void tic(){
		startTime = getCurrTime();
	}
	double toc(){
		return getCurrTime() - startTime;
	}
};
//
 
unsigned long xor128() {
        static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
        unsigned long t = (x ^ (x << 11));
        x = y; y = z; z = w;
        return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

struct state { int y, x; string path; };
static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
string dir = "RDLU";
map<char, int> dxdy;

int main() {
        TicToc tictoc;
        tictoc.tic();
        dxdy['R'] = 0;
        dxdy['D'] = 1;
        dxdy['L'] = 2;
        dxdy['U'] = 3;
        int n, k, h, w, t;
        scanf("%d %d %d %d %d", &n, &k, &h, &w, &t);
        vector<vector<string>> s(n, vector<string> (h));
        for (int i = 0; i < n; i ++) {
                for (int j = 0; j < h; j ++) {
                        cin >> s[i][j];
                }
        }
        string ans;
        vector<int> ans_choose;
        int ma = -1;
        for (int use = 0; use < n; use ++) {
                if (tictoc.toc() > 3.5) break;
                int sy, sx;
                for (int i = 0; i < h; i ++) {
                        for (int j = 0; j < w; j ++) {
                                if (s[use][i][j] == '@') {
                                        sy = i;
                                        sx = j;
                                }
                        }
                }
                int cury = sy, curx = sx;
                string prim;
                while (true) {
                        int d = xor128() % 4;
                        cury += dy[d];
                        curx += dx[d];
                        if (s[use][cury][curx] == 'x' || s[use][cury][curx] == '#') {
                                cury -= dy[d];
                                curx -= dx[d];
                                continue;
                        }
                        prim.push_back(dir[d]);
                        if (prim.size() >= 2500) break;
                }
                vector<pair<int, int>> res; //(score, index)
                for (int i = 0; i < n; i ++) {
                        vector<string> cur = s[i];
                        int cury, curx;
                        for (int j = 0; j < h; j ++) {
                                for (int k = 0; k < w; k ++) {
                                        if (cur[j][k] == '@') {
                                                cury = j;
                                                curx = k;
                                        }
                                }
                        }
                        vector<vector<bool>> used(h, vector<bool>(w, false));
                        int score = 0;
                        for (int j = 0; j < prim.size(); j ++) {
                                int d = dxdy[prim[j]];
                                cury += dy[d];
                                curx += dx[d];
                                if (cur[cury][curx] == 'x') break;
                                if (cur[cury][curx] == '#') {
                                        cury -= dy[d];
                                        curx -= dx[d];
                                }
                                else if (cur[cury][curx] == 'o') {
                                        if (!used[cury][curx]) {
                                                score ++;
                                        }
                                }
                                used[cury][curx] = true;
                        }
                        res.emplace_back(score, i);
                }
                sort(res.rbegin(), res.rend());
                int tot = 0;
                vector<int> choose;
                for (int i = 0; i < k; i ++) {
                        tot += res[i].first;
                        choose.push_back(res[i].second);
                }
                if (tot > ma) {
                        ans = prim;
                        ma = tot;
                        ans_choose = choose;
                }
        }
        for (int i = 0; i < ans_choose.size(); i ++) {
                cout << ans_choose[i] << (i == ans_choose.size() - 1 ? '\n' : ' ');
        }
        cout << ans << endl;
        return 0;
}        

Submission Info

Compile Error

./Main.cpp: In member function ‘double TicToc::getCurrTime()’:
./Main.cpp:35:25: error: ‘gettimeofday’ was not declared in this scope
   gettimeofday(&tv, NULL);
                         ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d %d", &n, &k, &h, &w, &t);
                                                    ^