結果
| 問題 | No.438 Cwwプログラミング入門 |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2016-10-29 00:14:22 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 7,649 bytes |
| コンパイル時間 | 1,360 ms |
| コンパイル使用メモリ | 118,792 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-27 21:55:37 |
| 合計ジャッジ時間 | 5,197 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 98 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>#include <functional>#include <set>#include <ctime>#include <random>#include <chrono>#include <cassert>using namespace std;namespace {using Integer = long long; //__int128;template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}template<class T> istream& operator , (istream& is, T& val){ return is >> val;}template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}template<class H> void print(const H& head){ cout << head; }template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }template<class H> void eprint(const H& head){ cerr << head; }template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }class range{long long start_, end_, step_;public:struct range_iterator{long long val, step_;range_iterator(long long v, long long step) : val(v), step_(step) {}long long operator * (){return val;}void operator ++ (){val += step_;}bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;}};range(long long len) : start_(0), end_(len), step_(1) {}range(long long start, long long end) : start_(start), end_(end), step_(1) {}range(long long start, long long end, long long step) : start_(start), end_(end), step_(step) {}range_iterator begin(){ return range_iterator(start_, step_); }range_iterator end(){ return range_iterator( end_, step_); }};string operator "" _s (const char* str, size_t size){ return move(string(str)); }constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexedmt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());template<class T> string join(const vector<T>& v, const string& sep){stringstream ss; for(int i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str();}string operator * (string s, int k){ if(k<=0) return ""; string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }}constexpr long long mod = 9_ten + 7;long long gcd(long long a, long long b){ return (b==0)?a:gcd(b,a%b); }template<class ... T> long long gcd(long long a, long long b, T ... c){ return gcd(gcd(a,b), c...);}long long lcm(long long a, long long b){ if(a<b) swap(a,b); return (b==1)?a:a*(b/gcd(a,b)); }template<class ... T> long long lcm(long long a, long long b, T ... c){ return lcm(lcm(a,b), c...);}long long extgcd(long long a, long long b, long long &x, long long &y){long long d=a;if(b!=0){d = extgcd(b, a%b, y, x);y -= (a/b) * x;}else{x = 1;y = 0;}return d;}#include <tuple>tuple<long long,long long,long long> check(long long a, long long b, long long& x, long long& y, long long k){tuple<long long,long long,long long> len = tuple<long long,long long,long long> {10000000,-1,-1};for(x=-10000*2; x<=10000*2; x++){long long rem = k - a*x;if(rem % b != 0) continue;y = rem / b;if(x == 0 && y== 0) continue;if(x<0 && y<0) continue;if( (abs(x) + abs(y)) * 2 - 1 > 10000*2) continue;len = min(len, tuple<long long,long long,long long>{ (abs(x) + abs(y)) * 2 - 1, x, y });}for(y=-10000*2; y<=10000*2; y++){long long rem = k - b*y;if(rem % a != 0) continue;x = rem / a;if(x == 0 && y== 0) continue;if(x<0 && y<0) continue;if( (abs(x) + abs(y)) * 2 - 1 > 10000*2) continue;len = min(len, tuple<long long,long long,long long>{ (abs(x) + abs(y)) * 2 - 1, x, y });}x = get<1>(len);y = get<2>(len);return len;}long long logic_machine(long long x, long long y, string& s){if(s=="mourennaihasimasenn") return -1;deque<int> dq;for(auto i : range(s.size()) ){if(s[i] == 'c') dq.push_back(x);else if(s[i] == 'w') dq.push_back(y);else if(s[i] == 'C'){long long a = dq.back(); dq.pop_back();long long b = dq.back(); dq.pop_back();dq.push_back(a+b);}else if(s[i] == 'W'){long long a = dq.back(); dq.pop_back();long long b = dq.back(); dq.pop_back();dq.push_back(a-b);}else{abort();}}if(dq.size() != 1) abort();return dq.back();}string solver(long long x, long long y, long long z){if((x==0 || y==0) && z==0){return ( x==0?"c" : "w");}if(x==0 && y==0 && z!=0){return ("mourennaihasimasenn");}if(x==0 && y!=0){if(z%y != 0){return ("mourennaihasimasenn");}else{int k = z/y;if(2*k-1 <= 10000){return ( "w"_s * k + "C"_s * (k-1) );}else{return ("mourennaihasimasenn");}}return 0;}if(y==0 && x!=0){if(z%x != 0){return ("mourennaihasimasenn");}else{int k = z/x;if(2*k-1 <= 10000){return ( "c"_s * k + "C"_s * (k-1) );}else{return ("mourennaihasimasenn");}}return 0;}long long u,v;auto l = check(x,y, u,v, z);eprintln( get<0>(l), get<1>(l), get<2>(l) );// long long un,ko;// long long g = extgcd(x,y, un,ko);// un *= z/g;// ko *= z/g;//assert( u!=0 || v!=0 );if( x*u + y*v != z ){if(z==0){return "ccW";}return ("mourennaihasimasenn");}if( (abs(u) + abs(v))*2 - 1 <= 10000 ){string ans;if(u>0){ans += "w"_s * abs(v);ans += "c"_s * abs(u);ans += "C"_s * (abs(u)-1);if(v>0){ans += "C"_s * abs(v);}else{ans += "W"_s * abs(v);}}else{ans += "c"_s * abs(u);ans += "w"_s * abs(v);ans += "C"_s * (abs(v)-1);if(u>0){ans += "C"_s * abs(u);}else{ans += "W"_s * abs(u);}}long long val = logic_machine(x,y,ans);eprintln(val);assert(val == z);return (ans);}else{return ("mourennaihasimasenn");}}int main(){long long x,y,z;cin >> x,y,z;auto ans1 = solver(x,y,z);println(ans1);// auto ans2 = solver(y,x,z);// if(ans1.size() > 10000){// ans1 = "mourennaihasimasenn";// }// if(ans2.size() > 10000){// ans2 = "mourennaihasimasenn";// }// for(auto& c : ans2){// if(c == 'c') c = 'w';// else if(c == 'w') c = 'c';// }// if((ans1 != "mourennaihasimasenn" || ans2 != "mourennaihasimasenn") &&// (ans1 == "mourennaihasimasenn" || ans2 == "mourennaihasimasenn")// ){// println(ans1 == "mourennaihasimasenn" ? ans2 : ans1);// }else{// println( ans1.size() < ans2.size() ? ans1 : ans2);// }return 0;}//💩