Код не проходит по тайм лимиту

@chaiz · Регистрация: 08.07.2022

Студворк — интернет-сервис помощи студентам

уже 3 часа мучаюсь
ребят помогите с кодом не проходит по тайм лимиту:
Формат входа. Первая строка содержит исходную строку S, вто-
рая — число запросов q. Каждая из последующих q строк задаёт
запрос тройкой чисел i, j, k и означает следующее: вырезать под-
строку S[i..j] (где i и j индексируются с нуля) и вставить её после
k-го символа оставшейся строки (где k индексируется с едини-
цы), при этом если k = 0, то вставить вырезанный кусок надо в
начало.
Формат выхода. Выведите полученную (после всех q запросов) стро-
ку.
Ограничения. S содержит только буквы латинского алфавита. 1 ≤
|S| ≤ 300 000; 1 ≤ q ≤ 100 000; 0 ≤ i ≤ j ≤ n−1; 0 ≤ k ≤ n−(j−i+1).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string S;
    int q;
    cin >> S >> q;
    S.reserve(S.length() + q); // резервируем память для добавления подстрок
    for (int i = 0; i < q; i++) {
        int i_pos, j_pos, k_pos;
        cin >> i_pos >> j_pos >> k_pos;
        string sub = S.substr(i_pos, j_pos - i_pos + 1);
        S.erase(i_pos, j_pos - i_pos + 1);
        if (k_pos == 0) {
            S = sub + S;
        } else if (k_pos <= S.length()) {
            S.insert(k_pos, sub);
        } else {
            S += sub;
        }
    }
    cout << S << endl;
    return 0;
}

@Kastaneda · 28.03.2023, 14:48

У тебя внутри цикла сложность 3n, если написать это все руками на сишных строках, то можно уложиться в 1n. Но основные тормоза мне кажется не в этом, операция ввода сильно тормозит. Есть пример ввода? Если там числа разделяются не enter'ом, а пробелом, то я бы всю строку q(i, j, k) сначала считал бы в строку и уже в коде бы ее разделял на числа. Это бы дало дикий прирост в скорости.

@chaiz · 28.03.2023, 15:10 **[ТС]**

Пример.
Вход:
3
2 1 2
1 -1 -1
3 -1 -1
Выход:
CORRECT

Пример.
Вход:
3
1 1 2
2 -1 -1
3 -1 -1
Выход:
INCORRECT

Добавлено через 5 минут
Kastaneda, не мог бы написать код что я понял ?

@Kastaneda · 28.03.2023, 15:14

Сообщение от chaiz

Пример.
Вход:
3
2 1 2
1 -1 -1
3 -1 -1
Выход:
CORRECT
Пример.
Вход:
3
1 1 2
2 -1 -1
3 -1 -1
Выход:
INCORRECT

Это не похоже на ввод/вывод этой задачи.

@chaiz · 28.03.2023, 15:56 **[ТС]**

ну в примере так

@Kastaneda · 29.03.2023, 06:13

Сообщение от chaiz

ну в примере так

Ну тогда покажи как оно матчится с описанием задачи в первом посте и с твоим кодом.

@chaiz · 29.03.2023, 23:45 **[ТС]**

уже решил

@vlisp · 30.03.2023, 13:41

Сообщение от Kastaneda

если написать это все руками на сишных строках, то можно уложиться в 1n

не удивлюсь если юудет еще медленнее

@Kastaneda · 30.03.2023, 14:14

Сообщение от vlisp

не удивлюсь если юудет еще медленнее

Можешь аргументировать? Ты думаешь у std::string там свой облачный аллокатор, который в х1000 быстрее и к которому доступ по секретной радуге, на спине у единорога?

Добавлено через 5 минут

Сообщение от chaiz

уже решил

Можешь поделиться решением? Просто интересно.

@vlisp · 30.03.2023, 14:20

Сообщение от Kastaneda

Можешь аргументировать?

Си строка - это линейный список символов. каждый доступ к i-тому элементу это i операций

@Kastaneda · 30.03.2023, 14:31

Сообщение от vlisp

Си строка - это линейный список символов. каждый доступ к i-тому элементу это i операций

Простите, вы из раздела ZeroCode сюда пришли?

@sourcerer · 30.03.2023, 14:56

vlisp, сишная строка - это не лист, это массив символов. Сколько бы элементов в массиве не было - доступ к конкретному элементу всегда О(1) - то есть, константный. То есть, ровно за одну операцию вы получите доступ к элементу по индексу - хоть в массиве из пяти сивмолов, хоть в массиве из пяти тысяч символов.

@vlisp · 30.03.2023, 16:26

Сообщение от sourcerer

То есть, ровно за одну операцию вы получите доступ к элементу по индексу - хоть в массиве из пяти сивмолов, хоть в массиве из пяти тысяч символов.

а длина строки?

@KSergey9 · 30.03.2023, 16:47

Сообщение от vlisp

а длина строки?

Она не нужна в подавляющем большинстве случаев

@vlisp · 30.03.2023, 16:54

Сообщение от KSergey9

Она не нужна в подавляющем большинстве случаев

в конкретно этом случае она вызывается на каждом шаге цикла

@Kastaneda · 30.03.2023, 17:11

Сообщение от vlisp

в конкретно этом случае она вызывается на каждом шаге цикла

Конкретно в этом слачае строка вводится 1 раз и ее длина всегда известна. Что мешает сделать для сишной строки так же?

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Kastaneda 5232 / 3205 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	28.03.2023, 14:48
	У тебя внутри цикла сложность 3n, если написать это все руками на сишных строках, то можно уложиться в 1n. Но основные тормоза мне кажется не в этом, операция ввода сильно тормозит. Есть пример ввода? Если там числа разделяются не enter'ом, а пробелом, то я бы всю строку q(i, j, k) сначала считал бы в строку и уже в коде бы ее разделял на числа. Это бы дало дикий прирост в скорости. 0

@chaiz 0 / 0 / 0 Регистрация: 08.07.2022 Сообщений: 85
	28.03.2023, 15:10 [ТС]
	Пример. Вход: 3 2 1 2 1 -1 -1 3 -1 -1 Выход: CORRECT Пример. Вход: 3 1 1 2 2 -1 -1 3 -1 -1 Выход: INCORRECT Добавлено через 5 минут Kastaneda, не мог бы написать код что я понял ? 0

@chaiz 0 / 0 / 0 Регистрация: 08.07.2022 Сообщений: 85
	28.03.2023, 15:56 [ТС]
	ну в примере так 0

@chaiz 0 / 0 / 0 Регистрация: 08.07.2022 Сообщений: 85
	29.03.2023, 23:45 [ТС]
	уже решил 0

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	30.03.2023, 14:56
	vlisp, сишная строка - это не лист, это массив символов. Сколько бы элементов в массиве не было - доступ к конкретному элементу всегда О(1) - то есть, константный. То есть, ровно за одну операцию вы получите доступ к элементу по индексу - хоть в массиве из пяти сивмолов, хоть в массиве из пяти тысяч символов. 0