Ideone.com

download

copy

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
// update 17/06/28 経路情報
// update 17/07/08 気持ち(手抜き)高速化
// update 17/07/15 サンプル追加  バグ修正
 
struct chktime{  //時間測定
	chrono::system_clock::time_point ctm;
	chktime() { reset();}
	void reset() { ctm=chrono::system_clock::now();}
	uint64_t gtm(){
		auto ptm = chrono::system_clock::now() - ctm;
		return chrono::duration_cast<chrono::milliseconds>(ptm).count();
	}
	void disp(){ cout <<"time(ms)="<< gtm() <<"\n";}
};
 
int16_t dp[(1<<26) +16], bf[(1<<26) +16];
int dvn[1050];
 
int cal(const string& str, vector<int>& ans){
 
	const int n = str.size();
	for(int i=0;i<1048;i++) dvn[i] = i / n;
	int si[30] ={};
	for(int i=0; i<n; ++i){
		si[i] = str[i] == '_' ? 0 : str[i] - '0';
	}
 
	memset(dp, 0x04, sizeof dp);// 0x0404 = 1028
	memset(bf, -1, sizeof bf);
 
	dp[0] = 0;
	int gl=0;
	for(int j=0; j<n; ++j) if(si[j] != 0) gl += 1<<j;
	for(int i=0; i< gl; ++i){
		for(int j=0; j<n; ++j)/* if(si[j] !=0 && !(i>>j &1))*/{//
			int mi = i | 1 << j;
			//int ptm = (dp[i] -j + n -1)/n; // n*ptm+j  食事開始可能時間
			//assert((dp[i] -j + n -1) < 1040 );
			int ptm = dvn[dp[i] -j + n -1]; //除算回避
			int cmx = n*ptm + j + si[j];
			if(dp[mi] > cmx){
				dp[mi] = cmx; bf[mi] = j;
			}
		}
	}
	// 経路情報復元
	for(int pf=gl; bf[pf] >= 0; pf -= 1<<bf[pf] ) ans.push_back(bf[pf]);
	reverse(ans.begin(), ans.end());
	return dp[gl];
}
 
void mpath(string str, const vector<int>& path){
 
	cout <<" 順番(index) : ";
	for(auto x: path) cout << x <<" ";
	cout <<endl;
	int cr=0, n=str.size();
 
	printf("%9s : %8s %8s %8s %8s :: status obj(n=%d)\n",
		"idx","wait","start","eating","end-time",n);
	for( auto pt : path){
		int ptm = ( cr -pt + n -1)/n;
		int stt = n*ptm+pt;  // = (cr/n + (cr%n > pt) ) *n + pt;
 
		int skj = str[pt] - '0';
		string dsp = str;
		dsp[pt]='S'; dsp[(pt+skj)%n]='E';
		printf ("%9d : %8d %8d %8d %8d",pt, stt-cr, stt, skj,  stt+ skj);
		printf (" :: %s\n", dsp.c_str());
		cr =  stt + skj; str[pt] = '_';
	}
	cout <<endl;
}
 
int main()
{
 
	chktime tma;
	string s;
	while(cin >> s){
		vector<int> jn;
		tma.reset();
		cout << s <<" ---> " <<cal(s, jn) <<endl;
		tma.disp();
		mpath(s, jn);
	}
 
	return 0;
}

I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoImF2eDIiKQogCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKLy8gdXBkYXRlIDE3LzA2LzI4IOe1jOi3r+aDheWgsQovLyB1cGRhdGUgMTcvMDcvMDgg5rCX5oyB44GhKOaJi+aKnOOBjSnpq5jpgJ/ljJYKLy8gdXBkYXRlIDE3LzA3LzE1IOOCteODs+ODl+ODq+i/veWKoCAg44OQ44Kw5L+u5q2jCiAKc3RydWN0IGNoa3RpbWV7ICAvL+aZgumWk+a4rOWumgoJY2hyb25vOjpzeXN0ZW1fY2xvY2s6OnRpbWVfcG9pbnQgY3RtOwoJY2hrdGltZSgpIHsgcmVzZXQoKTt9Cgl2b2lkIHJlc2V0KCkgeyBjdG09Y2hyb25vOjpzeXN0ZW1fY2xvY2s6Om5vdygpO30KCXVpbnQ2NF90IGd0bSgpewoJCWF1dG8gcHRtID0gY2hyb25vOjpzeXN0ZW1fY2xvY2s6Om5vdygpIC0gY3RtOwoJCXJldHVybiBjaHJvbm86OmR1cmF0aW9uX2Nhc3Q8Y2hyb25vOjptaWxsaXNlY29uZHM+KHB0bSkuY291bnQoKTsKCX0KCXZvaWQgZGlzcCgpeyBjb3V0IDw8InRpbWUobXMpPSI8PCBndG0oKSA8PCJcbiI7fQp9OwogCmludDE2X3QgZHBbKDE8PDI2KSArMTZdLCBiZlsoMTw8MjYpICsxNl07CmludCBkdm5bMTA1MF07CiAKaW50IGNhbChjb25zdCBzdHJpbmcmIHN0ciwgdmVjdG9yPGludD4mIGFucyl7CiAKCWNvbnN0IGludCBuID0gc3RyLnNpemUoKTsKCWZvcihpbnQgaT0wO2k8MTA0ODtpKyspIGR2bltpXSA9IGkgLyBuOwoJaW50IHNpWzMwXSA9e307Cglmb3IoaW50IGk9MDsgaTxuOyArK2kpewoJCXNpW2ldID0gc3RyW2ldID09ICdfJyA/IDAgOiBzdHJbaV0gLSAnMCc7Cgl9CiAKCW1lbXNldChkcCwgMHgwNCwgc2l6ZW9mIGRwKTsvLyAweDA0MDQgPSAxMDI4CgltZW1zZXQoYmYsIC0xLCBzaXplb2YgYmYpOwogCglkcFswXSA9IDA7CglpbnQgZ2w9MDsKCWZvcihpbnQgaj0wOyBqPG47ICsraikgaWYoc2lbal0gIT0gMCkgZ2wgKz0gMTw8ajsKCWZvcihpbnQgaT0wOyBpPCBnbDsgKytpKXsKCQlmb3IoaW50IGo9MDsgajxuOyArK2opLyogaWYoc2lbal0gIT0wICYmICEoaT4+aiAmMSkpKi97Ly8KCQkJaW50IG1pID0gaSB8IDEgPDwgajsKCQkJLy9pbnQgcHRtID0gKGRwW2ldIC1qICsgbiAtMSkvbjsgLy8gbipwdG0raiAg6aOf5LqL6ZaL5aeL5Y+v6IO95pmC6ZaTCgkJCS8vYXNzZXJ0KChkcFtpXSAtaiArIG4gLTEpIDwgMTA0MCApOwoJCQlpbnQgcHRtID0gZHZuW2RwW2ldIC1qICsgbiAtMV07IC8v6Zmk566X5Zue6YG/CgkJCWludCBjbXggPSBuKnB0bSArIGogKyBzaVtqXTsKCQkJaWYoZHBbbWldID4gY214KXsKCQkJCWRwW21pXSA9IGNteDsgYmZbbWldID0gajsKCQkJfQoJCX0KCX0KCS8vIOe1jOi3r+aDheWgseW+qeWFgwoJZm9yKGludCBwZj1nbDsgYmZbcGZdID49IDA7IHBmIC09IDE8PGJmW3BmXSApIGFucy5wdXNoX2JhY2soYmZbcGZdKTsKCXJldmVyc2UoYW5zLmJlZ2luKCksIGFucy5lbmQoKSk7CglyZXR1cm4gZHBbZ2xdOwp9CiAKdm9pZCBtcGF0aChzdHJpbmcgc3RyLCBjb25zdCB2ZWN0b3I8aW50PiYgcGF0aCl7CiAKCWNvdXQgPDwiIOmghueVqihpbmRleCkgOiAiOwoJZm9yKGF1dG8geDogcGF0aCkgY291dCA8PCB4IDw8IiAiOwoJY291dCA8PGVuZGw7CglpbnQgY3I9MCwgbj1zdHIuc2l6ZSgpOwogCglwcmludGYoIiU5cyA6ICU4cyAlOHMgJThzICU4cyA6OiBzdGF0dXMgb2JqKG49JWQpXG4iLAoJCSJpZHgiLCJ3YWl0Iiwic3RhcnQiLCJlYXRpbmciLCJlbmQtdGltZSIsbik7Cglmb3IoIGF1dG8gcHQgOiBwYXRoKXsKCQlpbnQgcHRtID0gKCBjciAtcHQgKyBuIC0xKS9uOwoJCWludCBzdHQgPSBuKnB0bStwdDsgIC8vID0gKGNyL24gKyAoY3IlbiA+IHB0KSApICpuICsgcHQ7CiAKCQlpbnQgc2tqID0gc3RyW3B0XSAtICcwJzsKCQlzdHJpbmcgZHNwID0gc3RyOwoJCWRzcFtwdF09J1MnOyBkc3BbKHB0K3Nraiklbl09J0UnOwoJCXByaW50ZiAoIiU5ZCA6ICU4ZCAlOGQgJThkICU4ZCIscHQsIHN0dC1jciwgc3R0LCBza2osICBzdHQrIHNraik7CgkJcHJpbnRmICgiIDo6ICVzXG4iLCBkc3AuY19zdHIoKSk7CgkJY3IgPSAgc3R0ICsgc2tqOyBzdHJbcHRdID0gJ18nOwoJfQoJY291dCA8PGVuZGw7Cn0KIAppbnQgbWFpbigpCnsKIAoJY2hrdGltZSB0bWE7CglzdHJpbmcgczsKCXdoaWxlKGNpbiA+PiBzKXsKCQl2ZWN0b3I8aW50PiBqbjsKCQl0bWEucmVzZXQoKTsKCQljb3V0IDw8IHMgPDwiIC0tLT4gIiA8PGNhbChzLCBqbikgPDxlbmRsOwoJCXRtYS5kaXNwKCk7CgkJbXBhdGgocywgam4pOwoJfQogCglyZXR1cm4gMDsKfQ==

Success #stdin #stdout 2.83s 277376KB

stdin

copy

14432
887654329
12_3
313__
4_35_1264_23_434
123456789123456789
88967472612377988186
19898693316679441672
93769682716711132249893
9376968271671113224912345

stdout

copy

14432 ---> 20
time(ms)=63
 順番(index) : 0 2 3 4 1 
      idx :     wait    start   eating end-time :: status obj(n=5)
        0 :        0        0        1        1 :: SE432
        2 :        1        2        4        6 :: _ES32
        3 :        2        8        3       11 :: _E_S2
        4 :        3       14        2       16 :: _E__S
        1 :        0       16        4       20 :: ES___

887654329 ---> 80
time(ms)=17
 順番(index) : 1 2 3 4 5 6 7 0 8 
      idx :     wait    start   eating end-time :: status obj(n=9)
        1 :        1        1        8        9 :: ES7654329
        2 :        2       11        7       18 :: E_S654329
        3 :        3       21        6       27 :: E__S54329
        4 :        4       31        5       36 :: E___S4329
        5 :        5       41        4       45 :: E____S329
        6 :        6       51        3       54 :: E_____S29
        7 :        7       61        2       63 :: E______S9
        0 :        0       63        8       71 :: S_______E
        8 :        0       71        9       80 :: ________E

12_3 ---> 6
time(ms)=19
 順番(index) : 0 1 3 
      idx :     wait    start   eating end-time :: status obj(n=4)
        0 :        0        0        1        1 :: SE_3
        1 :        0        1        2        3 :: _S_E
        3 :        0        3        3        6 :: __ES

313__ ---> 8
time(ms)=24
 順番(index) : 1 2 0 
      idx :     wait    start   eating end-time :: status obj(n=5)
        1 :        1        1        1        2 :: 3SE__
        2 :        0        2        3        5 :: E_S__
        0 :        0        5        3        8 :: S__E_

4_35_1264_23_434 ---> 60
time(ms)=23
 順番(index) : 0 5 7 13 2 6 11 15 3 8 14 10 
      idx :     wait    start   eating end-time :: status obj(n=16)
        0 :        0        0        4        4 :: S_35E1264_23_434
        5 :        1        5        1        6 :: __35_SE64_23_434
        7 :        1        7        6       13 :: __35__2S4_23_E34
       13 :        0       13        4       17 :: _E35__2_4_23_S34
        2 :        1       18        3       21 :: __S5_E2_4_23__34
        6 :        1       22        2       24 :: ___5__S_E_23__34
       11 :        3       27        3       30 :: ___5____4_2S__E4
       15 :        1       31        4       35 :: ___E____4_2___3S
        3 :        0       35        5       40 :: ___S____E_2___3_
        8 :        0       40        4       44 :: ________S_2_E_3_
       14 :        2       46        3       49 :: _E________2___S_
       10 :        9       58        2       60 :: __________S_E___

123456789123456789 ---> 98
time(ms)=27
 順番(index) : 0 1 3 7 15 4 9 10 12 16 6 13 2 5 11 14 8 17 
      idx :     wait    start   eating end-time :: status obj(n=18)
        0 :        0        0        1        1 :: SE3456789123456789
        1 :        0        1        2        3 :: _S3E56789123456789
        3 :        0        3        4        7 :: __3S567E9123456789
        7 :        0        7        8       15 :: __3_567S9123456E89
       15 :        0       15        7       22 :: __3_E67_9123456S89
        4 :        0       22        5       27 :: __3_S67_9E23456_89
        9 :        0       27        1       28 :: __3__67_9SE3456_89
       10 :        0       28        2       30 :: __3__67_9_S3E56_89
       12 :        0       30        4       34 :: __3__67_9__3S56_E9
       16 :        0       34        8       42 :: __3__6E_9__3_56_S9
        6 :        0       42        7       49 :: __3__6S_9__3_E6__9
       13 :        0       49        5       54 :: E_3__6__9__3_S6__9
        2 :        2       56        3       59 :: __S__E__9__3__6__9
        5 :        0       59        6       65 :: _____S__9__E__6__9
       11 :        0       65        3       68 :: ________9__S__E__9
       14 :        0       68        6       74 :: __E_____9_____S__9
        8 :        6       80        9       89 :: ________S________E
       17 :        0       89        9       98 :: ________E________S

88967472612377988186 ---> 149
time(ms)=67
 順番(index) : 0 8 17 18 6 13 1 9 10 12 2 11 16 4 14 3 19 5 15 7 
      idx :     wait    start   eating end-time :: status obj(n=20)
        0 :        0        0        8        8 :: S8967472E12377988186
        8 :        0        8        6       14 :: _8967472S12377E88186
       17 :        3       17        1       18 :: _8967472_12377988SE6
       18 :        0       18        8       26 :: _89674E2_12377988_S6
        6 :        0       26        7       33 :: _89674S2_1237E988__6
       13 :        0       33        7       40 :: E89674_2_1237S988__6
        1 :        1       41        8       49 :: _S9674_2_E237_988__6
        9 :        0       49        1       50 :: __9674_2_SE37_988__6
       10 :        0       50        2       52 :: __9674_2__S3E_988__6
       12 :        0       52        7       59 :: __9674_2___3S_988__E
        2 :        3       62        9       71 :: __S674_2___E__988__6
       11 :        0       71        3       74 :: ___674_2___S__E88__6
       16 :        2       76        8       84 :: ___6E4_2______98S__6
        4 :        0       84        7       91 :: ___6S4_2___E__98___6
       14 :        3       94        9      103 :: ___E_4_2______S8___6
        3 :        0      103        6      109 :: ___S_4_2_E_____8___6
       19 :       10      119        6      125 :: _____E_2_______8___S
        5 :        0      125        4      129 :: _____S_2_E_____8____
       15 :        6      135        8      143 :: ___E___2_______S____
        7 :        4      147        2      149 :: _______S_E__________

19898693316679441672 ---> 170
time(ms)=65
 順番(index) : 0 3 14 18 5 11 17 4 13 8 12 19 6 15 1 10 16 2 7 9 
      idx :     wait    start   eating end-time :: status obj(n=20)
        0 :        0        0        1        1 :: SE898693316679441672
        3 :        2        3        9       12 :: _98S86933166E9441672
       14 :        2       14        4       18 :: _98_8693316679S416E2
       18 :        0       18        7       25 :: _98_8E93316679_416S2
        5 :        0       25        6       31 :: _98_8S93316E79_416_2
       11 :        0       31        6       37 :: _98_8_93316S79_41E_2
       17 :        0       37        6       43 :: _98E8_93316_79_41S_2
        4 :        1       44        8       52 :: _98_S_93316_E9_41__2
       13 :        1       53        9       62 :: _9E___93316_7S_41__2
        8 :        6       68        3       71 :: _98___93S16E7__41__2
       12 :        1       72        7       79 :: _98___93_16_S__41__E
       19 :        0       79        2       81 :: _E8___93_16____41__S
        6 :        5       86        9       95 :: _98___S3_16____E1___
       15 :        0       95        4       99 :: _98____3_16____S1__E
        1 :        2      101        9      110 :: _S8____3_1E_____1___
       10 :        0      110        6      116 :: __8____3_1S_____E___
       16 :        0      116        1      117 :: __8____3_1______SE__
        2 :        5      122        8      130 :: __S____3_1E_________
        7 :       17      147        3      150 :: _______S_1E_________
        9 :       19      169        1      170 :: _________SE_________

93769682716711132249893 ---> 170
time(ms)=475
 順番(index) : 0 9 10 17 19 5 11 21 8 15 20 6 14 16 18 1 4 13 22 2 12 3 7 
      idx :     wait    start   eating end-time :: status obj(n=23)
        0 :        0        0        9        9 :: S37696827E6711132249893
        9 :        0        9        1       10 :: _37696827SE711132249893
       10 :        0       10        6       16 :: _37696827_S71113E249893
       17 :        1       17        2       19 :: _37696827__711132S4E893
       19 :        0       19        9       28 :: _3769E827__711132_4S893
        5 :        0       28        6       34 :: _3769S827__E11132_4_893
       11 :        0       34        7       41 :: _3769_827__S11132_E_893
       21 :        3       44        9       53 :: _3769_8E7___11132_4_8S3
        8 :        1       54        7       61 :: _3769_82S___111E2_4_8_3
       15 :        0       61        3       64 :: _3769_82____111S2_E_8_3
       20 :        2       66        8       74 :: _3769E82____111_2_4_S_3
        6 :        1       75        8       83 :: _3769_S2____11E_2_4___3
       14 :        0       83        1       84 :: _3769__2____11SE2_4___3
       16 :        1       85        2       87 :: _3769__2____11__S_E___3
       18 :        0       87        4       91 :: _3769__2____11____S___E
        1 :        2       93        3       96 :: _S76E__2____11________3
        4 :        0       96        9      105 :: __76S__2____1E________3
       13 :        0      105        1      106 :: __76___2____1SE_______3
       22 :        8      114        3      117 :: __E6___2____1_________S
        2 :        0      117        7      124 :: __S6___2_E__1__________
       12 :        3      127        1      128 :: ___6___2____SE_________
        3 :       13      141        6      147 :: ___S___2_E_____________
        7 :       21      168        2      170 :: _______S_E_____________

9376968271671113224912345 ---> 184
time(ms)=2051
 順番(index) : 1 5 11 18 22 0 9 10 17 20 21 24 8 15 19 6 14 16 23 4 13 2 12 3 7 
      idx :     wait    start   eating end-time :: status obj(n=25)
        1 :        1        1        3        4 :: 9S76E68271671113224912345
        5 :        1        5        6       11 :: 9_769S82716E1113224912345
       11 :        0       11        7       18 :: 9_769_82716S111322E912345
       18 :        0       18        4       22 :: 9_769_82716_111322S912E45
       22 :        0       22        3       25 :: E_769_82716_111322_912S45
        0 :        0       25        9       34 :: S_769_827E6_111322_912_45
        9 :        0       34        1       35 :: __769_827SE_111322_912_45
       10 :        0       35        6       41 :: __769_827_S_1113E2_912_45
       17 :        1       42        2       44 :: __769_827___11132S_E12_45
       20 :        1       45        1       46 :: __769_827___11132__9SE_45
       21 :        0       46        2       48 :: __769_827___11132__9_S_E5
       24 :        1       49        5       54 :: __76E_827___11132__9___4S
        8 :        4       58        7       65 :: __769_82S___111E2__9___4_
       15 :        0       65        3       68 :: __769_82____111S2_E9___4_
       19 :        1       69        9       78 :: __7E9_82____111_2__S___4_
        6 :        3       81        8       89 :: __769_S2____11E_2______4_
       14 :        0       89        1       90 :: __769__2____11SE2______4_
       16 :        1       91        2       93 :: __769__2____11__S_E____4_
       23 :        5       98        4      102 :: __E69__2____11_________S_
        4 :        2      104        9      113 :: __76S__2____1E___________
       13 :        0      113        1      114 :: __76___2____1SE__________
        2 :       13      127        7      134 :: __S6___2_E__1____________
       12 :        3      137        1      138 :: ___6___2____SE___________
        3 :       15      153        6      159 :: ___S___2_E_______________
        7 :       23      182        2      184 :: _______S_E_______________

https://ideone.com/PGKCb4

回転寿司 take2

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language