VI OIG zadanie dwa słowa

Mam problem z zadaniem z VI OIG pod tytułem: "Dwa słowa" Wywala mi limi czasowy na testach 5 7 9 przez co dostaje 66/100. Chciałem się Was spytać co robię źle, jak powinien wyglądać optymalny algorytm?

Oto mój kod:

#include <iostream>
#include <cstdio>

using namespace std;

int porownaj(char a[],char b[],int n, int indeks)//zwraca indeks wystepowania pierwszej sprzecznosci
{
	for(int i=indeks;i<n;i++)
		if(a[i]!=b[i])
			return i;
	return n;//oba teksty są takie same
}

int main(int argc, char *argv[])
{
	int n;//dlugosc każdego ze słów
	int z;//liczba dokonanych zamian
	int p1,p2;//zmienne pomocnicze wykorzystywane w pętli while
	int wynik;
	
	scanf("%d",&n);
	char a[n],b[n];//a-slowo pierwsze;b-slowo drugie
	scanf("%s",a);
	scanf("%s",b);
	scanf("%d",&z);

	
	
	int id = porownaj(a,b,n,0);//id-indeks roznicy;
	if(id==n)
		wynik=0;
	else if(a[id]<b[id])
		wynik=2;
	else
		wynik=1;		
	
	while(z--)
	{
		scanf("%d%d",&p1,&p2);	
		swap(a[p1],b[p2]);
		
		if(p1 <= id || p2 <= id)
		{
			id=porownaj(a,b,n,min(p1,p2));
			if(id==n)
				wynik=0;
			else if(a[id]<b[id])
				wynik=2;
			else
				wynik=1;			
		}
		printf("%d\n",wynik);
		
	}
	
	return 0;
}

Może tak uprościć:

#include <cstdio>
#include <cstring>
using namespace std;
 
int main()
  {
   char tb[]="201",*wyn=tb+1;
   unsigned n,z;
 
   scanf("%d",&n);   
   char a[n+1],b[n+1]; //z tym że nie powinno tak się robić - new lub malloc
   scanf("%s%s%d",a,b,&z);
   while(z--)
     {
      scanf("%d%d",&p1,&p2);        
      swap(a[p1],b[p2]);
      printf("%c\n",wyn[memcmp(a,b,n)]);
     }
   return 0;
  }

Tak a propos, wypadało by podać treść zadanie, możliwe że niepoprawnie odczytałem treść zadania z twojego kodu.

Treśc zadania znajdziesz na main.edu.pl w archiwach zadań potem olimpiada informatyczna gimnzjalistów potem olimpiada numer 6

Nadal przekroczenie limitu czasowego na tych samych testach

No to coś w ten deseń:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
  {
   unsigned n,z,t,w=0;
   scanf("%u",&n);   
   char *A=(char*)malloc(2n+2),*END=A+n,*B=END+1;
   scanf("%s%s%u",A,B,&z);
   t=n+1;
   while(z--)
     {
      unsigned p,q;
      scanf("%u%u",&p,&q);
      swap(A[p],B[q]);
      unsigned T=(p<q?p:q)*(t<=n);
      if(T<=t)
        {
         char *a=A+T,*b=B+T;
         while((*a==*b)&&(a<END)) { ++a; ++b; }
         t=A-a;
         w=(unsigned)('0'+(*a>*b)+((*a<*b)<<1));
        }
      puts((char*)&w);
     }
   return 0;
  }

http://main.edu.pl/pl/user.phtml?op=tests&c=10600&task=983
Spójrzcie na testy nr 5, 7 i 9. Ciężko byłoby wymyślić sensowną optymalizację bez ich znajomości.

ja bym zapamiętywał miejsce, w którym decyduje się wynik porównania leksykograficznego.
Jeśli ta liczba jest mniejsza niż a_i oraz b_i to zwracał ten sam wynik co ostatnio nie robiąc jakichkolwiek dodatkowych porównań.
Jeśli ta liczba jest większa bądź równa, to porównanie zacząłbym od miejsca min(a_i , b_i).

W sumie widzę, że Skrzyp_1997 tak zrobił :) .

@_13th_Dragon z tego wniosek, że trzeba zapamiętywać więcej niż jeden indeks.
Algorytm nadal ten sam, ale potrzebna jest jeszcze tablica indeksów o rozmiarze równym długości słów. W tej tablicy trzymamy indeks następnej komórki, dla których litery się różnią.
W ten sposób jeśli trzeba wykonać porównanie na bardzo długim odcinku to od razu można skoczyć do właściwego miejsca, które decyduje kolejności leksykograficznej (to jest jedyne miejsce, gdzie jeszcze można zaoszczędzić czas). Złożoność obliczeniowa (po przygotowaniu tablicy) spadnie z o(n) do o(1).

---

edit: pomysł z tablicą okazał się nietrafiony, ale tak czy owak należy trzymać listę różnic (set<int> z indeksami, gdzie są różnice powinien załatwić sprawę).

---

zapamiętując w `set<int>` indeksy, dla których są różnice, zaliczyłem wszystkie testy bez problemu (100/100 - najbardziej czasożerny test case 8 wykonałem w czasie 0.22s, reszta nie wolniej niż 0.05).