제출 #762223

#제출 시각아이디문제언어결과실행 시간메모리
762223minhcool자동 인형 (IOI18_doll)C++17
75.55 / 100
116 ms27128 KiB
//#define local #ifndef local #include "doll.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 5e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int cnt = 0; int c[N], x[N], y[N]; vector<int> nxts[N]; int rt; void create(int where, vector<int> v){ // cout << "OKOKOK " << where << " " << v.size() << "\n"; if(v.size() == 2){ // cout << v[0] << " " << v[1] << "\n"; x[where] = v[0], y[where] = v[1]; return; } vector<int> v1, v2; //cnt++; //x[where] = -cnt; for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]); bool ck = 0; for(auto it : v1) ck |= (it >= 0); if(ck){ cnt++; x[where] = -cnt; create(cnt, v1); } else x[where] = rt; for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]); ck = 0; for(auto it : v2) ck |= (it >= 0); if(ck){ cnt++; y[where] = -cnt; create(cnt, v2); } else y[where] = rt; } void create_circuit(int M, vector<int> A){ A.pb(0); for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]); c[0] = A[0]; int cntt = 0; for(int i = 1; i <= M; i++){ if(nxts[i].size() == 0) nxts[i].pb(1); if(nxts[i].size() <= 1){ c[i] = nxts[i][0]; continue; } int pw = 1; while(pw < nxts[i].size()) pw *= 2; cntt += (pw - 1); //cnt++; //c[i] = -cnt; //create(cnt, nxts[i]); } // cout << "HEHE " << cntt << "\n"; // cout << cntt << "\n"; int temp = cntt; for(int i = 1; i <= M; i++){ if(nxts[i].size() <= 1) continue; int pw = 1; while(pw < nxts[i].size()) pw *= 2; cnt++; c[i] = -cnt; rt = -cnt; if(pw > nxts[i].size()){ vector<int> nw; reverse(nxts[i].begin(), nxts[i].end()); int cnt = pw - nxts[i].size(); for(int j = 0; j < pw; j++){ if(!(j & 1)){ if(cnt){ nw.pb(rt); cnt--; } else{ // assert(nxts[i].size()); nw.pb(nxts[i].back()); nxts[i].pop_back(); } } else{ // assert(nxts[i].size()); nw.pb(nxts[i].back()); nxts[i].pop_back(); } } nxts[i] = nw; //reverse(nxts[i].begin(), nxts[i].end()); //cntt++; //reverse(nxts[i].begin(), nxts[i].end()); } //cnt++; create(cnt, nxts[i]); } /* for(int i = 1; i <= cnt; i++){ if(x[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); if(y[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); } for(int i = temp + 1; i <= cntt; i++){ x[i - (temp - cnt)] = x[i]; y[i - (temp - cnt)] = y[i]; }*/ // cout << cnt << "\n"; vector<int> C(M + 1), X(cnt), Y(cnt); for(int i = 0; i <= M; i++) C[i] = c[i]; for(int i = 1; i <= cnt; i++){ X[i - 1] = x[i], Y[i - 1] = y[i]; } answer(C, X, Y); } #ifdef local void process(){ } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) process(); } #endif

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
doll.cpp: In function 'void create(int, std::vector<int>)':
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]);
      |                   ~~~~~~~~^~~~~~~~~~
doll.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:97:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   if(pw > nxts[i].size()){
      |      ~~~^~~~~~~~~~~~~~~~
doll.cpp:89:6: warning: unused variable 'temp' [-Wunused-variable]
   89 |  int temp = cntt;
      |      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...