UVa1592 数据库（摘）

Output

For each dataset, if the table is in PNF write to the output file a single word ``YES" (without quotes). If the table is not in PNF, then write three lines. On the first line write a single word ``NO" (without quotes). On the second line write two integer row numbers r₁ andr₂ (1r₁,r₂n,r₁r₂), on the third line write two integer column numbers c₁ andc₂ (1c₁,c₂m,c1c2), so that values in columnsc₁ andc₂ are the same in rowsr₁ andr₂.

 Sample input

3 3
How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru
How to win ACM ICPC,Michael,michael@neerc.ifmo.ru
Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru
2 3
1,Peter,peter@neerc.ifmo.ru
2,Michael,michael@neerc.ifmo.ru

 Sample output

NO
2 3
2 3
YES

#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<vector>
using namespace std;

const int ROW = 10000 + 10;
const int COL = 10 + 5;
int n,m;
map<string, int> IDcache;
vector<string> Strcache;
vector<int> Text[ROW];           //处理后的文本，每个字符串都对应一个编号
struct node
{
    int x,y;
    node(int x, int y):x(x),y(y) { }
    bool operator < (const node& r) const{           //重载‘<‘
        return x<r.x || x==r.x&&y<r.y; 
    }       
};
map<node,int> data;

int f(string str)
{
    if(IDcache.count(str)) return IDcache[str];
    Strcache.push_back(str);
    return IDcache[str] = Strcache.size()-1;
}

void read()
{
    string str;
    char ch = getchar();
    for(int i=0;i<n;i++)
    {
        for(;;)
        {
            ch = getchar();
            if(ch==‘\n‘||ch==‘\r‘) {
                if(!str.empty()) Text[i].push_back(f(str));
                str.clear(); 
                break;
            }
            if(ch!=‘,‘) str += ch;
            else { 
                Text[i].push_back(f(str)); 
                str.clear();
            }
         }
    }
}

void solve()
{
    int x,y,c1,c2;
    for(c1=0;c1<m;c1++)
    {
        for(c2=c1+1;c2<m;c2++)
        {
            data.clear();
            for(int r=0;r<n;r++)
            {
                x = Text[r][c1]; y = Text[r][c2];
                node p(x,y);
                if(!data.count(p)) data[p] = r;
                else{
                    cout<<"NO"<<endl;
                    cout<<data[p]+1<<" "<<r+1<<endl<<c1+1<<" "<<c2+1<<endl;
                    return;
                }
            }
        }
    }
    cout<<"YES"<<endl;
}

int main()
{
    while(cin>>n>>m)
    {
        read();
        solve();
        for(int i=0;i<n;i++) Text[i].clear();
        IDcache.clear(); Strcache.clear();
    }
//system("pause");
    return 0;
}

UVa1592 数据库（摘）

标签：