1546A - AquaMoon and Two Arrays - CodeForces Solution


brute force greedy *800

Please click on ads to support us..

Python Code:

import sys

input = sys.stdin.readline
inf = float('inf')


def getInt():
    return int(input())


def getStr():
    return input().strip()


def getList(split=True):
    s = getStr()
    if split:
      s = s.split()
    return map(int, s)

t = getInt()


def solve():
    n = getInt()
    a = list(getList())
    b = list(getList())
    if sum(a) != sum(b):
      print(-1)
    else:
      res = []
      p = []
      q = []
      for i in range(n):
        diff = a[i] - b[i]
        if diff < 0 :
          q.extend([i+1] * -diff)
        elif diff > 0:
          p.extend([i+1] * diff )
      print(len(p))
      for i,j in zip(p, q):
        print(i,j)
                  
  

for _ in range(t):
    solve()

C++ Code:

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 10;
inline void solve() {
    int n, ans = 0, k = 0;
    
    scanf("%lld", &n);
    vector<int> a(n), b(n), c, d;
    c.clear(); d.clear();
    for(int i = 0; i < n; i++) cin>>a[i];
    for(int i = 0; i < n; i++) cin>>b[i];
    for(int i = 0; i < n; i++) {
        if(a[i] > b[i]) {
            for(int j = 1; j <= a[i] - b[i]; j++)
                c.push_back(i);
        }
        else if(a[i] < b[i]) {
            for(int j = 1; j <= b[i] - a[i]; j++)
                d.push_back(i);
        }
    }
    if(c.size() - d.size() != 0) cout << -1 << endl;
    else {
        cout << c.size() << endl;
        for(int i = 0; i < c.size(); i++) {
            cout << c[i] + 1 << " " << d[i] + 1 << endl;
        }
    }
    return ;
}
signed main() {
    int t; scanf("%lld", &t);
    while(t--) solve();
    return 0;
}
	   		 	   		 	 		 		 	 	  	 	


Comments

Submit
0 Comments
More Questions

796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings
677A - Vanya and Fence
1621A - Stable Arrangement of Rooks
472A - Design Tutorial Learn from Math
1368A - C+=
450A - Jzzhu and Children
546A - Soldier and Bananas
32B - Borze
1651B - Prove Him Wrong
381A - Sereja and Dima
41A - Translation
1559A - Mocha and Math
832A - Sasha and Sticks
292B - Network Topology
1339A - Filling Diamonds
910A - The Way to Home
617A - Elephant
48A - Rock-paper-scissors
294A - Shaass and Oskols
1213A - Chips Moving
490A - Team Olympiad
233A - Perfect Permutation
1360A - Minimal Square
467A - George and Accommodation