結果

問題 No.594 壊れた宝物発見機
ユーザー manuginomanugino
提出日時 2017-11-11 15:47:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 8,434 bytes
コンパイル時間 617 ms
コンパイル使用メモリ 87,860 KB
実行使用メモリ 24,048 KB
平均クエリ数 32.70
最終ジャッジ日時 2023-09-23 15:02:54
合計ジャッジ時間 4,124 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
24,036 KB
testcase_01 AC 107 ms
23,520 KB
testcase_02 AC 105 ms
23,856 KB
testcase_03 AC 109 ms
24,036 KB
testcase_04 AC 106 ms
23,844 KB
testcase_05 AC 107 ms
24,024 KB
testcase_06 AC 106 ms
23,652 KB
testcase_07 AC 104 ms
24,024 KB
testcase_08 AC 107 ms
23,220 KB
testcase_09 AC 106 ms
23,544 KB
testcase_10 AC 105 ms
23,676 KB
testcase_11 AC 105 ms
23,376 KB
testcase_12 AC 109 ms
23,652 KB
testcase_13 AC 105 ms
23,532 KB
testcase_14 AC 106 ms
23,640 KB
testcase_15 AC 107 ms
24,024 KB
testcase_16 AC 108 ms
24,048 KB
testcase_17 AC 106 ms
23,664 KB
testcase_18 AC 105 ms
24,036 KB
testcase_19 AC 106 ms
24,036 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define debug //*******************************************************************************************************************************************

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
// ２進数表示 = dout << static_cast<bitset<8> >(x)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




////////////////////////////////////////
//
////////////////////////////////////////


#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) dout << "%d\n", (A))
#define prints(A) dout << "%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(__w, (s), (g)) {disP(A[__w]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(__w, (s), (g)) {disP(__w);} dout << endl
#define line  dout << "----------------\n"
#define line2 dout << "================\n"

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0


typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int INF = (1LL<<31)-1;
//const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
//#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん

#define N_MAX 100010 //num of vertex or element
//#define M_MAX 124760 //num of edge
//#define DATA_MAX 1010


int mp[201][201][201];
int goal[3] = {9, -5, 85};


int a[3] = {0, 0, 0};


void init() {
    
    mp[goal[0]][goal[1]][goal[2]] = 0;
    
    int x = goal[0];
    int y = goal[1];
    int z = goal[2];
    
    
    //GOALを突き刺すz軸方向に更新
    for(z=goal[2]+1; z<=100; z++) {
        mp[x+100][y+100][z+100] = mp[x+100][y+100][z-1+100] + 1;
    }
    for(z=goal[2]-1; z>=-100; z--) {
        mp[x+100][y+100][z+100] = mp[x+100][y+100][z+1+100] + 1;
    }
    
    
    for(z=-100; z<=100; z++) {
        x = goal[0];
        y = goal[1];
        
        
        //y軸方向に更新
        for(y=goal[1]+1; y<=100; y++) {
            mp[x+100][y+100][z+100] = mp[x+100][y-1+100][z+100] + 1;
        }
        for(y=goal[1]-1; y>=-100; y--) {
            mp[x+100][y+100][z+100] = mp[x+100][y+1+100][z+100] + 1;
        }
        
        
        for(y=-100; y<=100; y++) {
            
            //x軸方向に更新
            for(x=goal[0]+1; x<=100; x++) {
                mp[x+100][y+100][z+100] = mp[x-1+100][y+100][z+100] + 1;
            }
            for(x=goal[0]-1; x>=-100; x--) {
                mp[x+100][y+100][z+100] = mp[x+1+100][y+100][z+100] + 1;
            }
            
        }
        
    }
    
    
}

void display() {
#ifdef debug
    dout << "------------------------- display() ---------------------\n";
    
    //    dout << "   "; showi(j,0,N+1);
    //    dout << "C[][] = \n";
    //    rep(i,0,N+1) {
    //        disP(i); dout << " : ";
    //        rep(j,0,N+1) {
    //            disP(C[i][j]);
    //        }
    //        dout << endl;
    //    }
    //    dout << endl;
    
    dout << "   "; showi(y,-10,11);
    dout << "z=" << goal[2] << "の、mp[x][y] = \n";
    rep(x,9,10) {
        disP(x); dout << " : ";
        rep(y,-10,11) {
            disP(mp[x+100][y+100][goal[2]+100]);
        }
        dout << endl;
    }
    dout << endl;
    
    
    
    dout << "------------------------- end of display() ---------------------\n";
#endif
}


// 質問クエリ
int ask(int x, int y, int z) {
    int d;
    cout << "?" << " " << x << " " << y << " " << z << endl;
    cin >> d;
    return d;
//    return mp[x+100][y+100][z+100];
}

// 回答クエリ
void answer(int x, int y, int z) {
    cout << "!" << " " << x << " " << y << " " << z << endl;
}


int binarySearch(int idx) {
    
    int l, m, r;
    int d_l, d_m, d_r;
    int tmp[3];
    
    rep(i,0,3) tmp[i] = a[i];
    
    l = -100;
    tmp[idx] = l;
    d_l = ask(tmp[0], tmp[1], tmp[2]);
    
    r = 100;
    tmp[idx] = r;
    d_r = ask(tmp[0], tmp[1], tmp[2]);
    
    for(m=(l+r)/2; l<r; m=(l+r)/2) {
        
#ifdef debug
        line;
        disp(l);
        disp(d_l);
        disp(r);
        disp(d_r);
        dout << endl;
        disp(m);
#endif
        
        tmp[idx] = m;
        d_m = ask(tmp[0], tmp[1], tmp[2]);
        
        
        if(d_l<d_r) {
            if(l+1==r) {
                r = l;
            }
            else {
                r = m;
                d_r = d_m;
            }
            
        } else {
            if(l+1==r) {
                l = r;
            }
            else {
                l = m;
                d_l = d_m;
            }
        }
    }
    
    return m;
    
}





int main() {
    
    //cin, coutの高速化  ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
    cin.tie(0); //cinとcoutの同期を切る
    ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
    
    //read input data
    
//    init();
//    display();
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
#endif
    //------------------------------------------------------------------------------------------
    
    
    rep(i,0,3) {
        a[i] = binarySearch(i);
    }
    
    
    answer(a[0], a[1], a[2]);
    
    
    
    
    
#ifdef debug
    dout << "=== OUTPUT ===\n";
    dout << "right answer = ";
    disP(goal[0]);
    disP(goal[1]);
    disP(goal[2]);
    dout << endl;
#endif
    
    
    
    
    
    
    
    
    
    
    
    //------------------------------------------------------------------------------------------
#ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#ifdef OUTPUTFILE
    cout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
#endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}
0