結果
問題 | No.471 直列回転機 |
ユーザー | chaemon |
提出日時 | 2016-12-22 01:24:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 401 ms / 3,141 ms |
コード長 | 4,373 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 172,840 KB |
実行使用メモリ | 24,336 KB |
平均クエリ数 | 19589.39 |
最終ジャッジ日時 | 2023-09-02 03:49:47 |
合計ジャッジ時間 | 15,703 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
24,192 KB |
testcase_01 | AC | 24 ms
23,904 KB |
testcase_02 | AC | 23 ms
23,280 KB |
testcase_03 | AC | 24 ms
24,024 KB |
testcase_04 | AC | 25 ms
23,496 KB |
testcase_05 | AC | 26 ms
24,168 KB |
testcase_06 | AC | 25 ms
23,532 KB |
testcase_07 | AC | 25 ms
23,496 KB |
testcase_08 | AC | 49 ms
23,400 KB |
testcase_09 | AC | 53 ms
23,412 KB |
testcase_10 | AC | 35 ms
23,916 KB |
testcase_11 | AC | 162 ms
24,180 KB |
testcase_12 | AC | 323 ms
23,928 KB |
testcase_13 | AC | 314 ms
24,036 KB |
testcase_14 | AC | 346 ms
23,940 KB |
testcase_15 | AC | 401 ms
23,532 KB |
testcase_16 | AC | 26 ms
23,520 KB |
testcase_17 | AC | 25 ms
24,264 KB |
testcase_18 | AC | 24 ms
23,376 KB |
testcase_19 | AC | 24 ms
23,424 KB |
testcase_20 | AC | 347 ms
23,952 KB |
testcase_21 | AC | 92 ms
24,012 KB |
testcase_22 | AC | 316 ms
23,544 KB |
testcase_23 | AC | 303 ms
24,132 KB |
testcase_24 | AC | 183 ms
23,256 KB |
testcase_25 | AC | 77 ms
23,484 KB |
testcase_26 | AC | 360 ms
23,424 KB |
testcase_27 | AC | 186 ms
23,904 KB |
testcase_28 | AC | 220 ms
24,336 KB |
testcase_29 | AC | 233 ms
23,244 KB |
testcase_30 | AC | 114 ms
23,268 KB |
testcase_31 | AC | 359 ms
23,628 KB |
testcase_32 | AC | 308 ms
23,412 KB |
testcase_33 | AC | 238 ms
23,628 KB |
testcase_34 | AC | 345 ms
23,412 KB |
testcase_35 | AC | 99 ms
24,156 KB |
testcase_36 | AC | 159 ms
23,880 KB |
testcase_37 | AC | 55 ms
23,412 KB |
testcase_38 | AC | 88 ms
23,268 KB |
testcase_39 | AC | 137 ms
23,916 KB |
testcase_40 | AC | 265 ms
23,928 KB |
testcase_41 | AC | 368 ms
23,916 KB |
testcase_42 | AC | 233 ms
23,640 KB |
testcase_43 | AC | 327 ms
24,012 KB |
testcase_44 | AC | 58 ms
23,916 KB |
testcase_45 | AC | 225 ms
24,144 KB |
testcase_46 | AC | 267 ms
23,244 KB |
testcase_47 | AC | 332 ms
23,844 KB |
testcase_48 | AC | 292 ms
23,916 KB |
testcase_49 | AC | 281 ms
23,652 KB |
testcase_50 | AC | 328 ms
24,036 KB |
testcase_51 | AC | 148 ms
23,508 KB |
testcase_52 | AC | 27 ms
24,192 KB |
testcase_53 | AC | 27 ms
24,012 KB |
testcase_54 | AC | 26 ms
23,904 KB |
testcase_55 | AC | 103 ms
24,024 KB |
testcase_56 | AC | 90 ms
23,640 KB |
testcase_57 | AC | 64 ms
23,256 KB |
testcase_58 | AC | 38 ms
23,376 KB |
ソースコード
// #includes {{{ #include <bits/stdc++.h> using namespace std; // }}} // pre-written code {{{ #define REP(i,n) for(int i=0;i<(int)(n);++i) #define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i) #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i) #define LET(x,a) __typeof(a) x(a) //#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i) #define ALL(c) (c).begin(), (c).end() #define MP make_pair #define EXIST(e,s) ((s).find(e)!=(s).end()) #define RESET(a) memset((a),0,sizeof(a)) #define SET(a) memset((a),-1,sizeof(a)) #define PB push_back #define DEC(it,command) __typeof(command) it=command //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl; const int INF=0x3f3f3f3f; typedef long long Int; typedef unsigned long long uInt; #ifdef __MINGW32__ typedef double rn; #else typedef long double rn; #endif typedef pair<int,int> pii; /* #ifdef MYDEBUG #include"debug.h" #include"print.h" #endif */ // }}} //{{{ mat typedef rn Num; typedef vector<Num> vec; typedef vector<vec> mat; //int /* Num add(const Num &x,const Num &y){return (x+y)%mod;} Num opposite(const Num &n){return ((-n)%mod+mod)%mod;} Num mul(const Num &x,const Num &y){return (unsigned long long)x*y%mod;} //Num inverse(const Num &n){return invMod(n,mod);} //Num modulo(const Num &n,int mod=::mod){return ((n+mod)%mod+mod)%mod;} */ //real number Num add(const Num &x,const Num &y){return x+y;} Num opposite(const Num &n){return -n;} Num mul(const Num &x,const Num &y){return x*y;} Num inverse(const Num &n){return 1L/n;} // O( n ) mat identity(int n) { mat A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n ) Num inner_product(const vec &a, const vec &b) { Num ans = 0; for (int i = 0; i < a.size(); ++i) ans = add(ans,mul(a[i],b[i])); return ans; } mat add(const mat &A, const mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < C.size(); ++i) for (int j = 0; j < C[i].size(); ++j) C[i][j] = add(A[i][j],B[i][j]); return C; } // O( n^2 ) vec mul(const mat &A, const vec &x) { vec y(A.size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) y[i] = add(y[i], mul(A[i][j],x[j])); return y; } // O( n^3 ) mat mul(const mat &A, const mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < C.size(); ++i) for (int j = 0; j < C[i].size(); ++j) for (int k = 0; k < A[i].size(); ++k) C[i][j] = add(C[i][j],mul(A[i][k],B[k][j])); return C; } // O( n^3 log e ) mat pow(const mat &A, long long e) { return e == 0 ? identity(A.size()) : e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1)); } //}}} //{{{ gauss int gauss(mat &A, vec &b) { //int gauss(mat& A) {//returns rank const int n=A.size(),m=A[0].size(); int pi=0; for(int pj=0;pj<m;pj++){ for(int i = pi+1; i < n; i++) { if (abs(A[i][pj]) > abs(A[pi][pj])) { swap(A[i], A[pi]); swap(b[i], b[pi]); } } if (abs(A[pi][pj]) > 0) { Num d = inverse(A[pi][pj]); REP(j, m) A[pi][j] = mul(A[pi][j],d); b[pi] = mul(b[pi],d); REP(i,n){ if(i==pi)continue; Num k = A[i][pj]; REP(j, m) A[i][j] = add(A[i][j],opposite(mul(k, A[pi][j]))); b[i] = add(b[i],opposite(mul(k, b[pi]))); } pi++; } } return pi; /* for(int i = pi; i < n; i++) if (abs(b[i]) > 0) throw Inconsistent(); if (pi < m || pj < m) throw Ambiguous(); for(int j = m-1; j >= 0; j--) REP(i, j) b[i] = modulo(b[i] - b[j] * A[i][j]); */ } //}}} int x[55555],y[55555]; int main(){ // printf("%.0Lf",12.34L); int M; scanf("%d",&M); REP(i,M){ scanf("%d%d",x+i,y+i); } const int T = 3; mat A(6,vec(6)); vec b(6); REP(i,T){ int x = rand()%20000-10000; int y = rand()%20000-10000; printf("? %d %d\n",x,y); fflush(stdout); long long a0,b0; scanf("%lld%lld",&a0,&b0); A[i*2][0] = (rn)x; A[i*2][1] = (rn)y; A[i*2][2] = 1.0L; A[i*2+1][3] = (rn)x; A[i*2+1][4] = (rn)y; A[i*2+1][5] = 1.0L; b[i*2] = (rn)a0; b[i*2+1] = (rn)b0; } gauss(A,b); printf("!\n"); REP(i,M){ printf("%.0Lf %.0Lf\n",b[0]*x[i]+b[1]*y[i]+b[2],b[3]*x[i]+b[4]*y[i]+b[5]); } fflush(stdout); return 0; }