UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215149#2656. addSTASISZHY100522ms33164kbC++112.4kb2024-11-26 20:23:162024-11-26 23:04:10

answer

// Problem: F. Restoring the Expression
// Contest: Codeforces - Codeforces Round 451 (Div. 2)
// URL: https://codeforces.com/problemset/problem/898/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 1e6 + 10, M = 1e6 + 10, mod1 = 10086001, mod2 = 998244353;

int n, m, q, ans;
int Hs1[N], Hs2[N], p1[N], p2[N];
string s;

// vector<int> e[N];

inline void init()
{
	p1[0] = p2[0] = 1;
	for(int i = 1; i <= n; i ++) p1[i] = p1[i - 1] * 10 % mod1, p2[i] = p2[i - 1] * 10 % mod2;
	for(int i = 1; i <= n; i ++) 
	{
		Hs1[i] = (Hs1[i - 1] * 10 + s[i] - '0') % mod1;
		Hs2[i] = (Hs2[i - 1] * 10 + s[i] - '0') % mod2;
	}
}

inline int calc1(int l, int r) {return ((Hs1[r] - Hs1[l - 1] * p1[r - l + 1]) % mod1 + mod1) % mod1;}
inline int calc2(int l, int r) {return ((Hs2[r] - Hs2[l - 1] * p2[r - l + 1]) % mod2 + mod2) % mod2;}

inline bool check(int l, int r)
{
	if(s[1] == '0' && l > 1) return false;
	if(s[l + 1] == '0' && r > l + 1) return false;
	if(s[r + 1] == '0' && n > r + 1) return false; 
	// cout << "ok0" << '\n';
	int suml1 = calc1(1, l), suml2 = calc2(1, l), sumr1 = calc1(l + 1, r), sumr2 = calc2(l + 1, r);
	int res1 = calc1(r + 1, n), res2 = calc2(r + 1, n);
	// cout << "l1 = " << suml1 << " l2 = " << suml2 << '\n';
	return (suml1 + sumr1) % mod1 == res1 && (suml2 + sumr2) % mod2 == res2;
	// int l1 = calc1(1, l), r1 = calc1(l + 1, r), res1 = calc1(r + 1, n);
	// return (l1 + r1) % mod1 == res1;
}

inline void print(int l, int r)
{
	for(int i = 1; i <= l; i ++) cout << s[i];
	cout << '+';
	for(int i = l + 1; i <= r; i ++) cout << s[i];
	cout << '=';
	for(int i = r + 1; i <= n; i ++) cout << s[i];
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s; n = s.size(), s = ' ' + s;	
	init();
	for(int i = 1; i <= n; i ++)
	{
		if(n - i <= i) break;
		for(int j = min(n - i, (n + i) / 2); j > i; j --)
		{
			if(j - i > n - j) continue;
			if(n - j > max(i, j - i) + 1) break;
			// cout << "i = " << i << " j = " << j << '\n';
			if(check(i, j))
			{
				// cout << "ok" << '\n';
				print(i, j);
				return 0;
			}
		}
	}
	// cout << (check(9, 18) ? "YES" : "NO") << '\n';
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1232kb

input:

93944386991110939443869921

output:

939443869911+10=939443869921

result:

ok single line: '939443869911+10=939443869921'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1236kb

input:

454431423351945476661

output:

45443142+33519=45476661

result:

ok single line: '45443142+33519=45476661'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1232kb

input:

807674775734008076747757340

output:

8076747757340+0=8076747757340

result:

ok single line: '8076747757340+0=8076747757340'

Test #4:

score: 5
Accepted
time: 1ms
memory: 1232kb

input:

47936157175791479437362

output:

479361571+75791=479437362

result:

ok single line: '479361571+75791=479437362'

Test #5:

score: 5
Accepted
time: 0ms
memory: 1232kb

input:

8684160719450790868416071945079

output:

868416071945079+0=868416071945079

result:

ok single line: '868416071945079+0=868416071945079'

Test #6:

score: 5
Accepted
time: 0ms
memory: 1232kb

input:

3150325920082064131504079841

output:

31503259200+820641=31504079841

result:

ok single line: '31503259200+820641=31504079841'

Test #7:

score: 5
Accepted
time: 31ms
memory: 27452kb

input:

9261598869160335057970310229283612818845075445997339978957735823966059362624832990688056822195031820...

output:

9261598869160335057970310229283612818845075445997339978957735823966059362624832990688056822195031820...

result:

ok single line: '926159886916033505797031022928...3054231497478113058482456217163'

Test #8:

score: 5
Accepted
time: 31ms
memory: 28264kb

input:

4701609646464966471786112512122938863110668626139644802941307402470417596440427343650542031038908331...

output:

4701609646464966471786112512122938863110668626139644802941307402470417596440427343650542031038908331...

result:

ok single line: '470160964646496647178611251212...8748395060129898210762369495747'

Test #9:

score: 5
Accepted
time: 40ms
memory: 32900kb

input:

9257202799561473086244723527541134302291247300137775651258683390946286052100443441136004200934466749...

output:

9257202799561473086244723527541134302291247300137775651258683390946286052100443441136004200934466749...

result:

ok single line: '925720279956147308624472352754...2243909924739032590362234901192'

Test #10:

score: 5
Accepted
time: 48ms
memory: 30444kb

input:

4416728326936622856150699213135191910979789931946758505266833530473668185681946524100519868737557117...

output:

4416728326936622856150699213135191910979789931946758505266833530473668185681946524100519868737557117...

result:

ok single line: '441672832693662285615069921313...3111611421682233543698480114264'

Test #11:

score: 5
Accepted
time: 40ms
memory: 32352kb

input:

3061041362133228009344583160193669358685821190644364754039063887060686947993153784177860432362852231...

output:

3061041362133228009344583160193669358685821190644364754039063887060686947993153784177860432362852231...

result:

ok single line: '306104136213322800934458316019...4042293112332153562949434601781'

Test #12:

score: 5
Accepted
time: 53ms
memory: 32352kb

input:

8531603642906385747583399978283975747482545589702570907905311483331351132043885935451850547243462360...

output:

8531603642906385747583399978283975747482545589702570907905311483331351132043885935451850547243462360...

result:

ok single line: '853160364290638574758339997828...5180929300855954383525415798317'

Test #13:

score: 5
Accepted
time: 43ms
memory: 32628kb

input:

3334731073815946487356418721839719459473953466541212185094515699104064312397044785650155583747481091...

output:

3334731073815946487356418721839719459473953466541212185094515699104064312397044785650155583747481091...

result:

ok single line: '333473107381594648735641872183...2104466046161989376727619609117'

Test #14:

score: 5
Accepted
time: 46ms
memory: 31532kb

input:

7113181137342253409543193679407457232222929505170124047879622285985297849800487899060254257891240998...

output:

7113181137342253409543193679407457232222929505170124047879622285985297849800487899060254257891240998...

result:

ok single line: '711318113734225340954319367940...7499580501189814539270742795615'

Test #15:

score: 5
Accepted
time: 39ms
memory: 32352kb

input:

2226576415518523623432262365703901892218433052474981493103118406267304359951441730045611163295598279...

output:

2226576415518523623432262365703901892218433052474981493103118406267304359951441730045611163295598279...

result:

ok single line: '222657641551852362343226236570...1283546754745341452795514550351'

Test #16:

score: 5
Accepted
time: 38ms
memory: 32072kb

input:

7282380568017210841065149843225478309106222219195648724985194189592224139941051182898879219925651713...

output:

7282380568017210841065149843225478309106222219195648724985194189592224139941051182898879219925651713...

result:

ok single line: '728238056801721084106514984322...6665028468440209585025731431738'

Test #17:

score: 5
Accepted
time: 48ms
memory: 33164kb

input:

6172023021615818261278406139291452768117320772111777913293782100858187571870407831738505138788606992...

output:

6172023021615818261278406139291452768117320772111777913293782100858187571870407831738505138788606992...

result:

ok single line: '617202302161581826127840613929...9022854228506784321805225740782'

Test #18:

score: 5
Accepted
time: 24ms
memory: 20376kb

input:

1641729471229192950020661455158841378773007409709289573050186474289570718374236969060246403530844480...

output:

1641729471229192950020661455158841378773007409709289573050186474289570718374236969060246403530844480...

result:

ok single line: '164172947122919295002066145515...1428289195899821981683641721297'

Test #19:

score: 5
Accepted
time: 17ms
memory: 14656kb

input:

6878197288916471551222877849454599200431985721720556540869310866854759368074574456390764568703818252...

output:

6878197288916471551222877849454599200431985721720556540869310866854759368074574456390764568703818252...

result:

ok single line: '687819728891647155122287784945...4028111836067678989020741708082'

Test #20:

score: 5
Accepted
time: 23ms
memory: 17112kb

input:

1336335135465815186373041570173603326293570642638147764739718555949768772153761126675803325646928488...

output:

1336335135465815186373041570173603326293570642638147764739718555949768772153761126675803325646928488...

result:

ok single line: '133633513546581518637304157017...5916651705852916207264857823016'