Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int mies_A[1000000+10];
- int mies_B[1000000+10];
- int pref_mies_A[1000000+10];
- int pref_mies_B[1000000+10];
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int l_mies_A;
- int l_mies_B;
- cin>>l_mies_A;
- cin>>l_mies_B;
- for(int i=0; i<l_mies_A; i++)
- cin>>mies_A[i];
- for(int i=0; i<l_mies_B; i++)
- cin>>mies_B[i];
- pref_mies_A[0] = mies_A[0];
- pref_mies_B[0] = mies_B[0];
- for(int i=1; i<l_mies_A; i++)
- pref_mies_A[i] = pref_mies_A[i-1] + mies_A[i];
- for(int i=1; i<l_mies_B; i++)
- pref_mies_B[i] = pref_mies_B[i-1] + mies_B[i];
- int zap;
- cin>>zap;
- int temp_1;
- int temp_2;
- char temp_3;
- int liczba_dni;
- int pocz;
- int konc;
- int mid;
- bool nast = 0;
- for(int x=0; x<zap; x++)
- {
- cin>>temp_1;
- cin>>temp_2;
- cin>>temp_3;
- if(temp_3 == 'A')
- {
- if(temp_2 == 1)
- liczba_dni = temp_1;
- else
- liczba_dni = temp_1 + pref_mies_A[temp_2-2];
- ///BINARY SEARCH
- pocz = 0;
- konc = l_mies_B-1;
- mid = (pocz+konc)/2;
- if(liczba_dni < pref_mies_B[0])
- cout<<liczba_dni<<" "<<1<<endl;
- else if(liczba_dni > pref_mies_B[l_mies_B-2])
- cout<<liczba_dni - pref_mies_B[l_mies_B-2]<<" "<<l_mies_B<<endl;
- else
- {
- do
- {
- if(pref_mies_B[mid-1] < liczba_dni && pref_mies_B[mid] >= liczba_dni)
- {
- cout<<liczba_dni - pref_mies_B[mid-1]<<" "<<mid+1<<endl;
- nast=1;
- }
- else if(pref_mies_B[mid] < liczba_dni)
- {
- pocz=mid;
- mid=(pocz+konc)/2;
- }
- else
- {
- konc=mid;
- mid=(pocz+konc)/2;
- }
- }while(nast==0);
- nast = 0;
- }
- }
- else
- {
- if(temp_2 == 1)
- liczba_dni = temp_1;
- else
- liczba_dni = temp_1 + pref_mies_B[temp_2-2];
- ///BINARY SEARCH
- pocz = 0;
- konc = l_mies_A-1;
- mid = (pocz+konc)/2;
- if(liczba_dni < pref_mies_A[0])
- cout<<liczba_dni<<" "<<1<<endl;
- else if(liczba_dni > pref_mies_A[l_mies_A-2])
- cout<<liczba_dni - pref_mies_A[l_mies_A-2]<<" "<<l_mies_A<<endl;
- else
- {
- do
- {
- if(pref_mies_A[mid-1] < liczba_dni && pref_mies_A[mid] >= liczba_dni)
- {
- cout<<liczba_dni - pref_mies_A[mid-1]<<" "<<mid+1<<endl;
- nast=1;
- }
- else if(pref_mies_A[mid] < liczba_dni)
- {
- pocz=mid;
- mid=(pocz+konc)/2;
- }
- else
- {
- konc=mid;
- mid=(pocz+konc)/2;
- }
- }while(nast==0);
- nast = 0;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement