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;
}
4
1 2 4 3
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.
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
With pleasure (∩_∩)~