Codeforces 988C(STL 사용)
4172 단어 CodeForcesSTL
제목:
C. Equal Sums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given kk sequences of integers. The length of the ii-th sequence equals to nini.
You have to choose exactly two sequences ii and jj (i≠ji≠j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence ii (its length will be equal to ni−1ni−1) equals to the sum of the changed sequence jj (its length will be equal to nj−1nj−1).
Note that it's required to remove exactly one element in each of the two chosen sequences.
Assume that the sum of the empty (of the length equals 00) sequence is 00.
Input
The first line contains an integer kk (2≤k≤2⋅1052≤k≤2⋅105) — the number of sequences.
Then kk pairs of lines follow, each pair containing a sequence.
The first line in the ii-th pair contains one integer nini (1≤ni<2⋅1051≤ni<2⋅105) — the length of the ii-th sequence. The second line of the ii-th pair contains a sequence of nini integers ai,1,ai,2,…,ai,niai,1,ai,2,…,ai,ni.
The elements of sequences are integer numbers from −104−104 to 104104.
The sum of lengths of all given sequences don't exceed 2⋅1052⋅105, i.e. n1+n2+⋯+nk≤2⋅105n1+n2+⋯+nk≤2⋅105.
Output
If it is impossible to choose two sequences such that they satisfy given conditions, print "NO"(without quotes). Otherwise in the first line print "YES"(without quotes), in the second line — two integers ii, xx (1≤i≤k,1≤x≤ni1≤i≤k,1≤x≤ni), in the third line — two integers jj, yy (1≤j≤k,1≤y≤nj1≤j≤k,1≤y≤nj). It means that the sum of the elements of the ii-th sequence without the element with index xx equals to the sum of the elements of the jj-th sequence without the element with index yy.
Two chosen sequences must be distinct, i.e. i≠ji≠j. You can print them in any order.
If there are multiple possible answers, print any of them.
Examples
input
Copy
2
5
2 3 1 3 2
6
1 1 2 2 2 1
output
Copy
YES
2 6
1 2
input
Copy
3
1
5
5
1 1 1 1 1
2
2 3
output
Copy
NO
input
Copy
4
6
2 2 2 2 2 2
5
2 2 2 2 2
3
2 2 2
5
2 2 2 2 2
output
Copy
YES
2 2
4 1
Note
In the first example there are two sequences [2,3,1,3,2][2,3,1,3,2] and [1,1,2,2,2,1][1,1,2,2,2,1]. You can remove the second element from the first sequence to get [2,1,3,2][2,1,3,2] and you can remove the sixth element from the second sequence to get [1,1,2,2,2][1,1,2,2,2]. The sums of the both resulting sequences equal to 88
, i.e. the sums are equal.
제목 설명:
너에게 k개의 서열을 줄게, i개의 서열에ni의 숫자가 있어.두 개의 서열 i와 서열 j가 존재할 수 있는지 물어보십시오. i번째 서열과 j번째 서열에서 각각 1개의 수를 삭제하여 그들의 화합을 동일하게 할 수 있습니다.
제목 분석:
이 문제는 stl의 종합적인 운용 문제라고 할 수 있다.
우선 우리는 k개 서열의 매 서열 n개수를 발견할 것이다. 그러면 최대 4e10개수를 저장해야 한다.그러나 일반적인 수조는 이렇게 많은 것을 저장할 수 없다.따라서 이 문제에서 우리는 stl의vector를 사용하여 숫자를 저장하는 것을 선택할 수 밖에 없다.
우리가 요구하는 것은 어느 서열의 어느 수를 삭제하는 것이기 때문에, 우리는 모든 서열의 수를 매거하고, 전체 값을 기록하고, 이 수의ai의 값을 빼고, 얻은 수를 맵에 기록한다.만약 이 값이 맵에 이미 나타났다면, 이전에도 통계가 있었다는 것을 증명하기 때문에 직접 답을 출력하면 된다.
만약에 이 값이 맵에 나타나지 않았다면 우리는 이 값을 표시하고 두 개의 맵으로 이번에 삭제된 몇 번째 서열의 몇 번째 수를 각각 기록하면 된다.
ps: 이 문제에서 주어진 수치는 마이너스가 존재할 수 있기 때문에 직접 수조를 따서 통을 만들면 RE를 초래할 수 있기 때문에 이 문제에서 맵으로만 기록할 수 있습니다!!
코드:
#include
#define maxn 200005
using namespace std;
typedef long long ll;
vectorvec[maxn];
mapbag1;
mapbag2;
mapbag3;
int main()
{
int k;
scanf("%d",&k);
ll sum=0;
for(int i=1;i<=k;i++){
int n;
scanf("%d",&n);
sum=0;
for(int j=0;j>num;
vec[i].push_back(num);
sum+=vec[i][j];
}
for (int j=0;j
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
문제 풀이 보고서 의 CodeForces 91B QueueOtherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.