ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1003. Parity

It's simple
Posted by Cat36 24 Oct 2008 21:22
//main logic

#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

map<int, bool>  exist;
map<int, bool>  odd;
map<int, int>  prev;

bool add(int a, int b,  bool c){//b>=a;
    if (!exist[b]){
      exist[b] = true;
      odd[b] = c;
      prev[b] = a;
      return true;
    };
    int  i = prev[b];
    if(i==a) return (odd[b]==c);
    if(i<a) return add(i,a-1, (c!=odd[b]));
    return add(a,i-1, (c!=odd[b]));
};
Re: It's simple
Posted by Aram Shatakhtsyan (YSU) 15 Feb 2009 20:37
Thank you very much, at least I solved it!
Nice problem!
Re: It's simple
Posted by nguyenductam 7 Apr 2010 07:29
thank you! i study very from you
Re: It's simple
Posted by BaJIuK 1 Nov 2011 16:49
Thanks! nice idea ;) I've got AC thank you very much!!!)

Edited by author 01.11.2011 17:53
Re: It's simple
Posted by robot1 9 Dec 2011 15:56
100
5
5 6 odd
7 8 odd
1 6 even
1 4 odd
7 8 even

why result is 3 and not 4?
Re: It's simple
Posted by scythe 13 Dec 2011 04:10
because 1 1 = 0 but 0 0 not 1

the input format is verrrry misleading, i have lost 2 hours of my live because of it.
Re: It's simple
Posted by robot1 16 Dec 2011 13:00
#include <stdio.h>
#include <map>
#include <iostream>
#include <string>
using namespace std;

map<int, bool>  exist;
map<int, bool>  odd;
map<int, int>  previous;

bool add(int a, int b,  bool c){//b>=a;
    if (!exist[b]){
      exist[b] = true;
      odd[b] = c;
      previous[b] = a;
      return true;
    };
    int  i = previous[b];
    if(i==a) return (odd[b]==c);
    if(i<a) return add(i,a-1, (c!=odd[b]));
    return add(a,i-1, (c!=odd[b]));
};

int main(int argc, char * argv[]) {
    while (1) {
        exist.clear();
        odd.clear();
        previous.clear();
        int numbers = 0;
        cin >> numbers;
        if (numbers==-1) break;
        int questions = 0;
        cin >> questions;
        bool flag = false;
        for (int i = 0; i<questions; i++) {
            int a = 0;
            cin >> a;
            int b = 0;
            cin >> b;
            string tmp;
            cin >> tmp;
            bool parity = false;
            if (tmp=="even") {
                parity = true;
            }
            if ((add(a,b,parity)==false)&&(flag==false)) {
                cout << i;
                flag=true;
            }
        }
        if (flag==false) {
            cout << questions;
        }
    }
    return 0;
}

What wrong? I got wa at 1 test.
Re: It's simple
Posted by vlyubin 1 Mar 2012 09:45
Then run it in the debug mode and you'll figure it out.
Re: It's simple
Posted by thefourtheye 21 Mar 2012 22:23
change
robot1 wrote 16 December 2011 13:00
            bool parity = false;
            if (tmp=="even") {
                parity = true;
            }
to
            bool parity = true;
            if (tmp=="even") {
                parity = false;
            }
and then break after flag=true;

Edited by author 21.03.2012 22:25

Edited by author 21.03.2012 22:25
Re: It's simple
Posted by khaihanhdk 2 May 2012 15:37
{
100
5
5 6 odd
7 8 odd
1 6 even
1 4 odd
7 8 even

why result is 3 and not 4?
}
I think the answer is 4, because [1,4] is odd and [5,6] is odd and [1,4],[5,6] are continuous then the answer isn't 3, but it is 4.

Edited by author 02.05.2012 15:37

Edited by author 02.05.2012 15:40

Edited by author 02.05.2012 15:40
Re: It's simple
Posted by Schullz 30 Oct 2012 19:12
Thanks a lot!
Re: It's simple
Posted by beta 19 Dec 2012 22:48
Good programing skills!! Thanks~
Re: It's simple
Posted by staticor 20 Jun 2013 23:08
remarkable code.
Re: It's simple
Posted by Sanfeng HU 15 Jul 2013 07:54
Pretty well!
Re: It's simple
Posted by Duy_e 17 Apr 2021 15:55
:0 this approach is out of my mind, great work!!