Блог пользователя Shuaib

Автор Shuaib, 14 лет назад, По-английски
Problem C:

I find the first two consecutive non equal integers, and check whether they are increase or decreasing. Then I look for the next integer that is in the opposite order. (Gives wrong answer on test 18)

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

int main()
{
long long n;
vector<long long> v;
cin>>n;
long long x;
for(long long i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}

if(v.size()<3)
{
cout<<0;
return 0;
}
else
{
int ind=0;
for(long long i=0;i<v.size();i++)
{
if(v[i+1]-v[i]!=0)
{
ind=i;
break;
}
}

for(long long i=ind+2;i<v.size();i++)
{
if((v[ind+1]-v[ind]>0 && v[i]-v[i-1]<0) || (v[ind+1]-v[ind]<0 && v[i]-v[i-1]>0))
{
cout<<"3"<<endl;
cout<<ind+1<<" "<<ind+2<<" "<<i+1;
return 0;
}

}
}
cout<<0;

return 0;
}


Problem D:

I maintain two adjacency matrices, one for connection outside the circle, and one for inside. When a new road is to be build, I check whether there is a road crossing inside/outside between the two cities. (Wrong answer on test 23) 

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

bool check(int x, int y, vector<vector<int> > & v)
{
if(x>y)
swap(x, y);
x=x-1;
y=y-1;
for(int i=x+1;i<y;i++)
{
for(int j=0;j<x;j++)
{
if(v[j][i]==1)
return false;
}
for(int j=y+1;j<v[0].size();j++)
{
if(v[j][i]==1)
return false;
}
}
v[x][y]=1;
v[y][x]=1;
return true;
}


int main()
{

int n, m;

cin>>n>>m;
vector<vector<int> > in(n, vector<int>(n, 0));
vector<vector<int> > out(n, vector<int>(n, 0));

int x, y;
vector<char> cv;
for(int i=0;i<m;i++)
{


cin>>x>>y;
if(check(x, y, in))
{
cv.push_back('i');
}
else if(check(x, y, out))
{
cv.push_back('o');
}
else {
cout<<"Impossible";
return 0;
}
}

for(int i=0;i<cv.size();i++)
{
cout<<cv[i];
}
return 0;
}

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For the problem C, try this test:
4
1 2 4 3
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
yes,just try adamax's example
the main mistake of your code is the third number totally depends on whether the first number is bigger or smaller than the second number that you find first.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
and the problem D ,I think it's a 2-SAT problem
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Thanks for the comment, kyno.yang! I am going to look into problem D in detail later. But I was wondering what's wrong with my approach.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Consider a situation that if a road both fit outside and inside , your code will put it into inside matrix,this will lead some aftereffects, it maybe conflict whit the next roads . But if you put it into outside matrix maybe is better.
      you can try this test
      6 4
      1 3
      4 6
      3 5
      2 4

  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    D is a simple graph coloring problem.